Advertisement
Guest User

Untitled

a guest
Jan 21st, 2020
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.54 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
  4. #define FORD(i,a,b) for(int i = (a); i >= (b); --i)
  5. #define mini(a,b) a=min(a,b)
  6. #define maxi(a,b) a=max(a,b)
  7. //#define sz(a) (int) a.size()
  8. #define mp make_pair
  9. #define pb push_back
  10. #define st first
  11. #define nd second
  12. typedef vector<int> vi;
  13. typedef long long ll;
  14. typedef long double ld;
  15. typedef pair<int, int> pii;
  16. const int N = 1e6+2;
  17.  
  18. int n,m;
  19. vector<int> V[N],R[N];
  20. // topsort;
  21. stack<int> s;
  22. bitset<N> o,o2;
  23. int war[N];
  24. int kl;
  25.  
  26. void addEdge(int a, int b) {
  27.     V[a].pb(b);
  28.     R[b].pb(a);
  29. }
  30.  
  31. void wczytaj() {
  32.     ios_base::sync_with_stdio(0);
  33.     cin.tie(0);
  34.     int a,b;
  35.     cin>>n>>m;
  36.     FOR(i,1,m) {
  37.         cin>>a>>b;
  38.         addEdge(a,b);
  39.     }
  40. }
  41.  
  42. void dfs(int p) {
  43.     o[p]=1;
  44.     for(int i=0; i<V[p].size(); ++i)
  45.         if(!o[V[p][i]]) dfs(V[p][i]);
  46.     s.push(p);
  47. }
  48.  
  49. void puscdfsy() {
  50.     FOR(i,1,n) {
  51.         if(!o[i]) dfs(i);
  52.     }
  53. }
  54.  
  55. void revdfs(int p) {
  56.     o2[p]=1;
  57.     war[s.top()]=kl;
  58.     s.pop();
  59.     for(int i=0; i<R[p].size(); ++i)
  60.         if(!o2[R[p][i]]) revdfs(R[p][i]);
  61. }
  62.  
  63. void skladowe() {
  64.     int w;
  65.     while(!s.empty()) {
  66.         w=s.top();
  67.         ++kl;
  68.         revdfs(w);
  69.     }
  70. }
  71.  
  72. void odpowiedz() {
  73.     int q,a,b;
  74.     cin>>q;
  75.     FOR(i,1,q) {
  76.         cin>>a>>b;
  77.         if(war[a]==war[b]) cout<<"MISJA UDANA\n";
  78.         else cout<<"MISJA NIEUDANA\n";
  79.     }
  80. }
  81.  
  82. signed main() {
  83.     wczytaj();
  84.     puscdfsy();
  85.     skladowe();
  86.     odpowiedz();
  87.     return 0;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement