fork(1) download
copy 
  1. //Bridges in a Graphs
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<iostream>
  5. #include<vector>
  6. #include<stack>
  7. #include<utility>
  8. #include<cstdlib>
  9. #include<algorithm>
  10. using namespace std;
  11. #define MAX 205
  12. int parent[MAX],timer=0,low[MAX],disc[MAX];
  13. bool vis[MAX];
  14. vector<pair<int,int> >st;
  15. vector<vector<int> >G(MAX);
  16. bool cmp(const pair<int,int> a,pair<int,int> b)
  17. {
  18. 	if(a.first==a.second)
  19. 	return a.second<b.second;
  20. 	else
  21. 	return a.first<b.first;
  22. }
  23. void reset()
  24. {
  25. 	st.clear();
  26. 	memset(parent,-1,sizeof parent);
  27. 	memset(vis,false,sizeof vis);
  28. 	for(int i=0;i<=MAX;i++)
  29. 	G[i].clear();
  30. }
  31. void dfs(int u)
  32. {	
  33. 	vis[u]=true;
  34. 	disc[u]=low[u]=timer++;
  35. 	for(int i=0;i<G[u].size();i++)
  36. 	{
  37. 		int v=G[u][i];
  38. 		if(!vis[v])
  39. 		{
  40. 			parent[v]=u;
  41. 			dfs(v);
  42. 			low[u]=min(low[u],low[v]);
  43. 			if(low[v]>low[u])
  44. 			st.push_back(make_pair(min(u,v),max(u,v)));
  45. 		}
  46. 		else if(v!=parent[u])
  47. 			low[u]=min(low[u],disc[v]);
  48. 	}
  49. }
  50. int main()
  51. {
  52. 	int n,t=0;
  53.  
  54. 	while(cin>>n)
  55. 	{
  56. 		reset();
  57. 		if(t>0)
  58. 		cout<<endl;
  59. 		if(n==0)
  60. 		{
  61. 			cout<<"0"<<" critical links\n";break;
  62. 		}
  63. 		int node,count;
  64.  
  65. 		for(int j=0;j<n;j++)
  66. 		{
  67. 			scanf("%d (%d)",&node,&count);
  68. 			for(int i=0;i<count;i++)
  69. 			{
  70. 				int x;
  71. 				scanf("%d",&x);
  72. 				G[node].push_back(x);
  73. 				G[x].push_back(node);
  74. 			}
  75. 		}
  76. 		for(int i=0;i<n;i++)
  77. 		{
  78. 			if(!vis[i])
  79. 			dfs(i);
  80. 		}
  81. 		sort(st.begin(),st.end(),cmp);
  82. 		cout<<st.size()<<" critical links\n";
  83.  
  84. 		for(int i=0;i<st.size();i++)
  85. 		cout<<st[i].first<<" - "<<st[i].second<<endl;
  86. 		t++;
  87.  
  88. 	}
  89. }
Success #stdin #stdout 0s 2868KB
comments (?)
stdin
copy 
8
0 (1) 1
1 (3) 2 0 3
2 (2) 1 3
3 (3) 1 2 4
4 (1) 3
7 (1) 6
6 (1) 7
5 (0)
0
stdout
copy 
3 critical links
0 - 1
3 - 4
6 - 7

0 critical links
https://ideone.com/Fpn6pd
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 years 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!