fork(1) download 
  1. #include<bits/stdc++.h>
  2. #define REP(i,n) for (int i = 1; i <= n; i++)
  3. #define mod 1000000007
  4. #define pb push_back
  5. #define ff first
  6. #define ss second
  7. #define ii pair<int,int>
  8. #define vi vector<int>
  9. #define vii vector<ii>
  10. #define lli long long int
  11. #define INF 1000000000
  12. #define endl '\n'
  13. const double PI = 3.141592653589793238460;
  14. typedef std::complex<double> Complex;
  15. typedef std::valarray<Complex> CArray;
  16.  
  17. using namespace std;
  18. set<int> ar[100001];
  19. vii bridges;
  20. int in[100001] , low[100001] , vis[100001];
  21. int timer;
  22.  
  23.  
  24. //code for finding bridges can be found at https://c...content-available-to-author-only...s.com/graph/bridge-searching.html
  25. //below function is also the implementation of the same algorithm
  26. void dfs(int node , int p = -1)
  27. {
  28. 	vis[node] = 1;
  29. 	in[node] = low[node] = timer++;
  30. 	for(int child : ar[node])
  31. 	{
  32. 		if(child == p) continue;
  33.  
  34. 		if(vis[child])
  35. 		low[node] = min(low[node] , in[child]);
  36.  
  37. 		else
  38. 		{
  39. 			dfs(child , node);
  40. 			low[node] = min(low[node] , low[child]);
  41.  
  42. 			if(low[child] > in[node])	//this edge is a bridge
  43. 			{
  44. 				bridges.pb({node , child});
  45. 			}
  46. 		}
  47. 	}
  48. }
  49.  
  50. // function to mark all the elements from the same connected component
  51. void dfs0(int node)
  52. {
  53. 	vis[node] = 1;
  54. 	for(int child : ar[node])
  55. 	if(!vis[child])
  56. 	dfs0(child);
  57. }
  58.  
  59.  
  60. //function returns true if a cycle is found
  61. bool hasCycle(int node ,int p = -1)
  62. {
  63. 	vis[node] = 1;
  64. 	for(int child : ar[node])
  65. 	if(child != p)
  66. 	{
  67. 		if(vis[child])
  68. 		return true;
  69.  
  70. 		if(hasCycle(child , node))
  71. 		return true;
  72. 	}
  73.  
  74. 	return false;
  75. }
  76.  
  77. int main()
  78. {
  79. 	int n , m , x , y ,t;
  80. 	cin>>t;
  81. 	while(t--)
  82. 	{
  83. 		cin>>n>>m , timer = 0 , bridges.clear();
  84. 		REP(i , n) ar[i].clear() , vis[i] = 0;
  85. 		REP(i , m)
  86. 		{
  87. 			cin>>x>>y;
  88. 			ar[x].insert(y) , ar[y].insert(x);
  89.  		}
  90.  
  91.  
  92. 		//finding all the bridges
  93.  		REP(i , n)
  94.  		if(!vis[i])
  95.  		dfs(i);
  96.  
  97.  
  98.  		//removing all the bridges
  99.  		for(ii e : bridges)
  100.  		ar[e.ff].erase(e.ss) , ar[e.ss].erase(e.ff);
  101.  		REP(i , n) vis[i] = 0;
  102.  
  103.  		//counting CC with cycles
  104.  		int cycleCount = 0;
  105.  		REP(i , n)
  106.  		if(ar[i].size() > 0 && !vis[i])
  107.  		dfs0(i) , cycleCount++;
  108.  
  109.  
  110.  		if(cycleCount != 1)
  111.  		cout<<"-1\n";
  112.  		else
  113.  		{
  114.  			int maxDegree = 0;
  115.  			int resNode = INF;
  116.  
  117.  
  118.  			//finding node with highest degree
  119.  			REP(i , n)
  120.  			if(ar[i].size() > maxDegree)
  121.  			maxDegree = ar[i].size() , resNode = i;
  122.  			else
  123.  			if(ar[i].size() == maxDegree)
  124.  			resNode = min(resNode , i);
  125.  
  126.  
  127.  			//removing all the edges of the highest degree node
  128.  			REP(i , n) ar[i].erase(resNode) , vis[i] = 0;
  129.  			ar[resNode].clear();
  130.  
  131.  
  132.  			//checking if no cycle exist
  133.  			REP(i , n)
  134.  			if(!vis[i])
  135.  			{
  136.  				if(hasCycle(i))
  137.  				{
  138.  					//if a cucle is found res sould be -1
  139.  					resNode = -1;
  140.  					break;
  141. 				}
  142. 			}
  143.  			cout<<resNode<<endl;
  144. 		}
  145. 	}
  146. }
  147.  
Success #stdin #stdout 0s 8424KB
comments ()
stdin 
5
5 5
5 1
5 2
1 2
2 3
2 4
5 6
4 5
4 1
4 2
4 3
5 1
5 2
5 5
3 4
3 5
3 1
3 2
4 2
4 1
3 4
6 6
1 2
2 3
3 1
4 5
5 6
6 4
stdout 
1
4
2
-1
-1
https://ideone.com/BvmdKN
FAILURE : Codechef NOV19 Long challenge
language:
C++14 (gcc 8.3)
created:
5 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!