fork download 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<int> graf[100005];
  6. int odw[100005];
  7. int gdzie[100005];
  8. int rep[100007];
  9.  
  10. int Find(int a){
  11.  
  12. 	if(rep[a] == a){
  13. 		return a;
  14. 	}
  15. 	rep[a] = Find(rep[a]);
  16. 	return (rep[a]);
  17. }
  18.  
  19.  
  20. int Union(int a,int b){
  21.     if(Find(a) == Find(b))
  22.     {
  23.         rep[Find(a)] = rep[Find(b)];
  24.         return 1;
  25.     }
  26.  
  27. 	rep[Find(a)] = rep[Find(b)];
  28. 	return 0;
  29. }
  30.  
  31. void dfs(int w,int od,int dor)
  32. {
  33.     odw[w] = 1;
  34.     for(int i : graf[w])
  35.     {
  36.         if(w == od && i == dor) continue;
  37.         if(w == dor && i == od) continue;
  38.         if(odw[i] == 0)
  39.         {
  40.             dfs(i,od,dor);
  41.             gdzie[i] = w;
  42.         }
  43.     }
  44. }
  45.  
  46. int main()
  47. {
  48.     ios_base::sync_with_stdio(0);
  49.     int n,m,a,b,x,y;
  50.     cin >> n >> m;
  51.     for(int i = 0;i < m;++i)
  52.     {
  53.         cin >> a >> b;
  54.         graf[a].push_back(b);
  55.         graf[b].push_back(a);
  56.         if(Union(a,b) == 1)
  57.         {
  58.         	x =a;y=b;
  59.  
  60.         }
  61.     }
  62.     dfs(x,x,y);
  63.     gdzie[x] = y;
  64.     int l = rep[Find(1)];
  65.     for(int i = 1; i <= n;++i)
  66.     {
  67.     	if(gdzie[i] == 0)
  68.     	{
  69.     		cout << "NIE";
  70.     		return 0;
  71.     	}
  72.     	if(rep[Find(i)] != l){ cout << "NIE"; return 0; }
  73.     }
  74.     cout << "TAK" << endl;
  75.     for(int i = 1; i <= n;++i)
  76.     {
  77.     	cout << gdzie[i] << endl;
  78.     }
  79.  
  80.  
  81.  
  82. }
Success #stdin #stdout 0.01s 5988KB
comments (?)
stdin 
5 5
1 2
2 3
1 4
4 5
2 5
stdout 
TAK
2
5
2
1
4
https://ideone.com/VFZzPZ
language:
C++14 (gcc 8.3)
created:
10 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!