Advertisement
Guest User

Untitled

a guest
Jan 21st, 2020
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.44 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement