fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. vector<int> g[100005];
  4. int cnt = 1,low[100005],num[100005],scc_end[100005];
  5. void dfs(int u,int p){
  6. 	low[u] = num[u] = cnt;
  7. 	++cnt;
  8. 	for(auto v : g[u]){
  9. 		if(v == p) continue;
  10. 		if(num[v] == 0){
  11. 			dfs(v,u);
  12. 			low[u] = min(low[u],low[v]);
  13. 		}else{
  14. 			low[u] = min(low[u],num[v]);
  15. 		}
  16. 	}
  17. 	scc_end[u] = cnt-1;
  18. }
  19. int main(){
  20. 	int n,q;
  21. 	cin >> n >> q;
  22. 	int p[n];
  23. 	for(int i = 1; i <= n;++i){
  24. 		cin >> p[i];
  25. 		g[i].push_back(p[i]);
  26. 	}
  27. 	g[1].push_back(2);
  28. 	g[2].push_back(1);
  29. 	for(int i = 1; i <= n;++i){
  30. 		if(num[i] == 0){
  31. 			dfs(i,i);
  32. 		}
  33. 	}
  34. 	while(q--){
  35. 		int x,y;
  36. 		cin >> x >> y;
  37. 		if((low[x] <= low[y] && low[y] <= scc_end[x])||(low[y] <= low[x] && low[x] <= scc_end[y])){
  38. 		    cout <<"YES\n";
  39. 		}
  40. 		else cout <<"NO\n";
  41. 	}
  42. }
Success #stdin #stdout 0.01s 6328KB
comments (?)
stdin
copy 
4 2 
1 4 3 2 
4 1 
3 4
stdout
copy 
YES
NO
https://ideone.com/iLQQ7i
language:
C++14 (gcc 8.3)
created:
16 days ago
visibility:
public

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!