fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define gc getchar_unlocked
  4. #define fo(i,n) for(i=0;i<n;i++)
  5. #define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
  6. #define ll long long
  7. #define si(x) scanf("%d",&x)
  8. #define sl(x) scanf("%lld",&x)
  9. #define ss(s) scanf("%s",s)
  10. #define pi(x) printf("%d\n",x)
  11. #define pl(x) printf("%lld\n",x)
  12. #define ps(s) printf("%s\n",s)
  13. #define pb push_back
  14. #define mp make_pair
  15. #define F first
  16. #define S second
  17. #define all(x) x.begin(), x.end()
  18. #define clr(x) memset(x, 0, sizeof(x))
  19. #define sortall(x) sort(all(x))
  20. #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
  21. #define PI 3.1415926535897932384626
  22. typedef pair<int, int> pii;
  23. typedef pair<ll, ll> pl;
  24. typedef vector<int> vi;
  25. typedef vector<ll> vl;
  26. typedef vector<pii> vpii;
  27. typedef vector<pl> vpl;
  28. typedef vector<vi> vvi;
  29. typedef vector<vl> vvl;
  30. int mpow(int base, int exp);
  31. void ipgraph(int m);
  32. void dfs(int u);
  33. void dfs1(int u);
  34. void dfs2(int u);
  35. const int mod = 1000000007;
  36. const int N = 3e5, M = 50003;
  37. //=======================
  38. bitset<M> bit[M];
  39. vi g[N], G[N], dag[N];
  40. int cmp[N], vis[N];
  41. int a[N];
  42. int n, m, q, T;
  43. vi top;
  44. struct xxx{
  45. int t, x, y;
  46. void in(){
  47. cin >> t >> x >> y;
  48. }
  49. }Q[N];
  50. void read(){
  51. int i;
  52. cin >> n >> m;
  53. ipgraph(m);
  54. cin >> q;
  55. Fo(i, 1, q+1){
  56. Q[i].in();
  57. int x = Q[i].x, y = Q[i].y;
  58. if(Q[i].t == 1){
  59. n++;
  60. if(y == 0){
  61. //x to n
  62. g[x].pb(n);
  63. G[n].pb(x);
  64. }
  65. else{
  66. //n to x
  67. g[n].pb(x);
  68. G[x].pb(n);
  69. }
  70. }
  71. }
  72. }
  73. void markSCC(){
  74. int i;
  75. clr(vis);
  76. Fo(i, 1, n+1){
  77. if(!vis[i]) dfs(i);
  78. }
  79. reverse(all(top));
  80. clr(vis);
  81. for(int u: top){
  82. if(!vis[u]){
  83. T++;
  84. dfs1(u);
  85. }
  86. }
  87. }
  88. void compressSCC(){
  89. int i;
  90. Fo(i, 1, 1+n){
  91. for(int v: g[i]){
  92. if(cmp[i] == cmp[v]) continue;
  93. dag[cmp[i]].pb(cmp[v]);
  94. }
  95. }
  96. }
  97. int main()
  98. {
  99. ios_base::sync_with_stdio(false);
  100. cin.tie(NULL);
  101. int i,k,j;
  102. read();
  103. markSCC();
  104. compressSCC();
  105.  
  106. //Now initialise bitsets for every component
  107. Fo(i, 1, T+1){
  108. bit[i] = 0;
  109. bit[i].set(i, 1);
  110. }
  111. //Now fill in the bitsets
  112. clr(vis);
  113. Fo(i, 1, T+1){
  114. if(!vis[i]) dfs2(i);
  115. }
  116. vi ans;
  117. //Answering queries
  118. Fo(i, 1, q+1){
  119. if(Q[i].t == 2){
  120. ans.pb(bit[cmp[Q[i].x]].test(cmp[Q[i].y]));
  121. }
  122. }
  123. for(int x: ans) cout << (x?"Yes":"No") << endl;
  124.  
  125. return 0;
  126. }
  127.  
  128. void ipgraph(int m){
  129. int i, u, v;
  130. fo(i, m){
  131. cin>>u>>v;
  132. u++, v++;
  133. g[u-1].pb(v-1);
  134. G[v-1].pb(u-1);
  135. }
  136. }
  137.  
  138. void dfs(int u){
  139. vis[u] = 1;
  140. for(int v:g[u]){
  141. if (vis[v]) continue;
  142. dfs(v);
  143. }
  144. top.pb(u);
  145. }
  146. void dfs1(int u){
  147. cmp[u] = T;
  148. vis[u] = 1;
  149. for(int v:G[u]){
  150. if (vis[v]) continue;
  151. dfs1(v);
  152. }
  153. }
  154. void dfs2(int u){
  155. vis[u] = 1;
  156. for(int v:dag[u]){
  157. if (vis[v]) continue;
  158. dfs2(v);
  159. }
  160. for(int v:dag[u]){
  161. bit[u] |= bit[v];
  162. }
  163. }
Success #stdin #stdout 0s 349696KB
stdin
4 4
1 2
1 3
2 4
3 4
5
1 2 0
2 3 5
2 1 5
1 1 1
2 6 4
stdout
No
Yes
Yes