fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n,m,u,v,d,num[20005],low[20005],par[20005],child,asdf=1;
  6. vector<int> adjlist[20005];
  7. vector< pair< int, int> > out;
  8. bool flag;
  9. char q,p;
  10.  
  11. void dfs(int now)
  12. {
  13. 	num[now]=d;
  14. 	low[now]=d;
  15. 	d++;
  16. 	child=0;
  17. 	flag=false;
  18. 	for(int i=0;i<adjlist[now].size();i++)
  19. 	{
  20. 		int next=adjlist[now][i];
  21. 		if(num[next]==-1)
  22. 		{
  23. 			par[next]=now;
  24. 			dfs(next);
  25. 			child++;
  26. 			if(low[next]>num[now])
  27. 			{
  28. 				int mini=min(now,next);
  29. 				int maks=max(now,next);
  30. 				out.push_back(make_pair(mini,maks));
  31. 			}
  32. 			low[now]=min(low[now],low[next]);
  33. 		}
  34. 		else if(next!=par[now])
  35. 		{
  36. 			low[now]=min(low[now],num[next]);
  37. 		}
  38. 	}
  39. }
  40.  
  41. int main()
  42. {
  43. 	while(cin>>n)
  44. 	{
  45. 		d=0;
  46. 		memset(num,-1,sizeof(num));
  47. 		memset(low,-1,sizeof(low));
  48. 		out.clear();
  49. 		for(int i=0;i<n;i++)
  50. 		{
  51. 			adjlist[i].clear();
  52. 		}
  53. 		for(int i=0;i<n;i++)
  54. 		{
  55. 			par[i]=i;
  56. 		}
  57.  
  58. 		for(int i=0;i<n;i++)
  59. 		{
  60. 			cin>>u>>q>>m>>p;
  61. 			for(int j=0;j<m;j++)
  62. 			{
  63. 				cin>>v;
  64. 				adjlist[u].push_back(v);
  65. 				adjlist[v].push_back(u);
  66. 			}
  67. 		}
  68.  
  69. 		for(int i=0;i<n;i++)
  70. 		{
  71. 			if(num[i]==-1)
  72. 			{
  73. 				dfs(i);
  74. 			}
  75. 		}
  76. 		sort(out.begin(),out.end());
  77. 		if(asdf>1)
  78. 		cout<<endl;
  79. 		cout<<out.size()<<" critical links"<<endl;
  80. 		for(int i=0;i<out.size();i++)
  81. 		{
  82. 			cout<<out[i].first<<" - "<<out[i].second<<endl;
  83. 		}
  84. 		asdf++;
  85. 	}
  86. 	cout<<endl;
  87. }
Success #stdin #stdout 0s 15944KB
comments (?)
stdin
copy 
2
0 (1) 1
1 (1) 0

20
0 (1) 1
1 (4) 0 2 4 5
2 (4) 1 5 6 10
3 (1) 4
4 (4) 1 3 5 8
5 (6) 1 2 4 8 9 10
6 (3) 2 10 13
7 (1) 8
8 (4) 4 5 7 9
9 (3) 5 8 10
10 (4) 2 5 9 6
11 (3) 12 13 17
12 (3) 11 14 15
13 (5) 6 11 14 17 18
14 (4) 12 13 15 18
15 (4) 12 14 16 18
16 (1) 15
17 (3) 11 13 19
18 (3) 13 14 15
19 (1) 17

19
0 (2) 1 2
1 (2) 0 3
2 (2) 0 3
3 (3) 1 2 4
4 (6) 5 6 3 10 7 8
5 (2) 4 6
6 (2) 5 4
7 (3) 9 8 4
8 (2) 4 7
9 (1) 7
10 (3) 11 12 4
11 (2) 10 13
12 (2) 10 13
13 (3) 11 12 14
14 (3) 13 15 16
15 (2) 14 16
16 (4) 14 15 17 18
17 (2) 16 18
18 (2) 16 17

7
0 (4) 1 2 3 4
1 (3) 0 2 3
2 (3) 1 0 3
3 (4) 0 1 2 4
4 (4) 0 3 6 5
5 (1) 4
6 (1) 4
stdout
copy 
1 critical links
0 - 1

6 critical links
0 - 1
3 - 4
6 - 13
7 - 8
15 - 16
17 - 19

4 critical links
3 - 4
4 - 10
7 - 9
13 - 14

2 critical links
4 - 5
4 - 6
https://ideone.com/r0IxlU
language:
C++14 (gcc 8.3)
created:
4 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!