fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN=200005;
  4. bool vis[MAXN];
  5. vector<int> g[MAXN],ord;
  6. void dfs(int u)
  7. {
  8. 	if(vis[u])return;
  9. 	vis[u]=1;
  10. 	for(auto& v : g[u])dfs(v);
  11. 	ord.push_back(u);
  12. }
  13. int p[MAXN],res[MAXN];
  14. vector<pair<int,int>> e[MAXN];
  15. int main()
  16. {
  17. 	int n,m;
  18. 	scanf("%d%d",&n,&m);
  19. 	for(int i=1;i<=n;i++)
  20. 		scanf("%d",&p[i]);
  21. 	for(int i=1;i<=m;i++)
  22. 	{
  23. 		int u,v;
  24. 		scanf("%d%d",&u,&v);
  25. 		e[u].emplace_back(v,i);
  26. 		e[v].emplace_back(u,i);
  27. 	}
  28. 	for(int i=1;i<=n;i++)
  29. 	{
  30. 		if(vis[i])continue;
  31. 		vector<int> cir;
  32. 		int t=i;
  33. 		do
  34. 		{
  35. 			cir.push_back(t);
  36. 			vis[t]=1;
  37. 			t=p[t];
  38. 		}
  39. 		while(!vis[t]);
  40. 		for(size_t j=0;j<cir.size();j++)
  41. 			res[cir[j]]=j;
  42. 		for(auto u : cir)
  43. 		{
  44. 			sort(e[u].begin(),e[u].end(),[&](auto& x,auto& y){
  45. 				return (res[x.first]-res[u]+cir.size())%cir.size()
  46. 					 < (res[y.first]-res[u]+cir.size())%cir.size();
  47. 			});
  48. 			for(size_t j=0;j+1<e[u].size();j++)
  49. 				g[e[u][j].second].push_back(e[u][j+1].second);
  50. 		}
  51. 	}
  52. 	memset(vis,0,(m+1)*sizeof(vis[0]));
  53. 	for(int i=1;i<=m;i++)
  54. 		if(!vis[i])dfs(i);
  55. 	reverse(ord.begin(),ord.end());
  56. 	for(int i=0;i<m;i++)
  57. 		printf("%d%c",ord[i]," \n"[i+1==m]);
  58. 	return 0;
  59. }
Success #stdin #stdout 0.01s 14740KB
comments (?)
stdin
copy 
6 4
6 5 1 3 2 4
3 1
2 5
6 3
6 4
stdout
copy 
4 2 1 3
https://ideone.com/EFosZn
language:
C++ (gcc 8.3)
created:
1 year 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!