SHARE
TWEET

Untitled

a guest Jan 21st, 2020 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
  6. #define FORD(i,a,b) for(int i = (a); i >= (b); --i)
  7. #define RI(i,n) FOR(i,1,(n))
  8. #define REP(i,n) FOR(i,0,(n)-1)
  9. #define mini(a,b) a=min(a,b)
  10. #define maxi(a,b) a=max(a,b)
  11. #define mp make_pair
  12. #define pb push_back
  13. #define st first
  14. #define nd second
  15. #define sz(w) (int) w.size()
  16. typedef vector<int> vi;
  17. typedef long long ll;
  18. typedef long double ld;
  19. typedef pair<ll, ll> pii;
  20. typedef pair<pii, int> para;
  21. const ll inf = 1e18 + 7;
  22. const int maxN = 1e6 + 5;  
  23.  
  24. int n, m, q;
  25. vi graph[maxN], graphRev[maxN];
  26. int cnt[maxN], t;
  27. bool used[maxN];
  28. vi vec;
  29.  
  30. void DFS(int v) {
  31.     used[v] = true;
  32.     for (auto x: graph[v]) {
  33.         if (!used[x]) {
  34.             DFS(x);
  35.         }
  36.     }
  37.     vec.pb(v);
  38. }
  39.  
  40. void DFSRev(int v) {
  41.     used[v] = true;
  42.     cnt[v] = t;
  43.     for (auto x: graphRev[v]) {
  44.         if (!used[x]) {
  45.             DFSRev(x);
  46.         }
  47.     }
  48. }
  49.  
  50. void SSS() {
  51.     RI(i, n) {
  52.         if (!used[i])
  53.             DFS(i);
  54.     }
  55.     RI(i, n) used[i] = false;
  56.     reverse(vec.begin(), vec.end());
  57.     for (auto v: vec) {
  58.         if (!used[v]) {
  59.             DFSRev(v);
  60.             t++;
  61.         }
  62.     }
  63. }
  64.  
  65. int main() {
  66.     ios_base::sync_with_stdio(0);
  67.     cin >> n >> m;
  68.     REP(_, m) {
  69.         int a, b;
  70.         cin >> a >> b;
  71.         graph[a].pb(b);
  72.         graphRev[b].pb(a);
  73.     }
  74.     SSS();
  75.     cin >> q;
  76.     REP(_, q) {
  77.         int a, b;
  78.         cin >> a >> b;
  79.         if (cnt[a] == cnt[b]) {
  80.             cout << "MISJA UDANA\n";
  81.         } else {
  82.             cout << "MISJA NIEUDANA\n";
  83.         }
  84.     }
  85.     return 0;
  86. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top