fork(5) download
copy 
  1. /*Author: Rishul Aggarwal*/
  2.  
  3. #include<bits/stdc++.h>
  4.  
  5. #define mod 1000000007
  6. #define ll long long
  7. #define rep(i,a,b) for(int i=a;i<=b;i++)
  8. #define in(type,x) scanf("%" #type,&x)
  9. #define debug(args...) {dbg,args; cerr<<endl;}
  10. #define test int t;\
  11. in(d,t);\
  12. while(t--)
  13.  
  14. using namespace std;
  15.  
  16. struct debugger
  17. {template<typename T> debugger& operator,(const T& v)
  18. {cerr<< v <<" ";
  19. return *this;
  20. }
  21. }dbg;
  22.  
  23. ll gcd(ll a,ll b) {if(b==0) return a; return gcd(b,a%b);}
  24.  
  25. ll power(ll b,ll exp,ll m) {ll ans=1; b%=m; while(exp){if(exp&1) ans=(ans*b)%m; exp>>=1; b=(b*b)%m; } return ans; }
  26.  
  27. vector<vector<int> >g;
  28. bool visited[1002];
  29. int a[1002];  	  
  30.  
  31. void dfs_recur(int start,vector<int>& comp,vector<int>& pos)
  32. {
  33. 	visited[start]=1;
  34. 	comp.push_back(a[start]);
  35. 	pos.push_back(start);
  36. 	int sz=g[start].size();
  37. 	rep(i,0,sz-1)
  38. 	 if(!visited[g[start][i]])
  39. 	  dfs_recur(g[start][i],comp,pos);
  40. }
  41.  
  42.  
  43. void dfs(int start,int n)
  44. {
  45. 	rep(i,1,n) visited[i]=0;
  46. 	rep(i,1,n)
  47. 	{
  48. 		if(!visited[i])
  49. 		{
  50. 		 vector<int> comp,pos;	
  51. 		 dfs_recur(i,comp,pos);
  52. 		 int sz=comp.size();
  53. 		 /*cout<<"component -> ";
  54. 		 rep(i,0,sz-1) cout<<pos[i]<<" - "<<comp[i]<<" ";
  55. 		 cout<<endl;*/
  56. 		 sort(comp.begin(),comp.end());
  57. 		 rep(i,0,sz-1) a[pos[i]]=comp[i];
  58. 	    }
  59. 	}
  60. }
  61.  
  62.  
  63. int main()
  64. {
  65.   test
  66.   {
  67.   	int n,m;
  68.   	in(d,n),in(d,m);
  69.  
  70.   	rep(i,1,n)
  71.   	 in(d,a[i]);
  72.  
  73.   	g.resize(1002);
  74. 	g.clear();
  75. 	rep(i,1,m)
  76. 	{
  77. 		int x,y;
  78. 		in(d,x),in(d,y);
  79. 		g[x].push_back(y),g[y].push_back(x);
  80. 	}
  81. 	dfs(1,n);
  82. 	rep(i,1,n) printf("%d ",a[i]);   
  83.     printf("\n");
  84.   }
  85.  
  86.   return 0;
  87. }
  88.  
Success #stdin #stdout 0s 3448KB
comments (?)
stdin
copy 
2
3 1
3 2 1
2 3
4 2
2 4 3 1
1 3
3 4
stdout
copy 
3 1 2 
1 4 2 3
https://ideone.com/mJsLSq
language:
C++14 (gcc 8.3)
created:
11 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!