fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
No
Yes
Yes
https://ideone.com/Fmw7vR
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!