fork(1) download
copy 
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<string.h>
  4. #include<sstream>
  5. #define max 200
  6. #define active 1
  7. #define initial 0
  8. #define finished 2
  9. int adj[max][max];
  10. int te[max][max];
  11. int be[max][max];
  12. int cl[max][max];
  13. int status[max];
  14. int dtime[max];
  15. int ftime[max];
  16. int tme,n,cnt;
  17. using namespace std;
  18. void dfs(int v)
  19. {
  20. 	status[v]=active;
  21. 	dtime[v]=++tme;
  22. 	for(int i=0;i<n;i++)
  23. 	{
  24. 		if(adj[v][i]==1)
  25. 		{
  26. 			if(status[i]==initial)
  27. 			{
  28. 				te[v][i]=1;
  29. 				dfs(i);
  30. 			}
  31. 			if(status[i]==active&&te[i][v]!=1)
  32. 			{
  33. 				be[v][i]=1;
  34. 			}
  35.  
  36. 		}
  37. 	}
  38. 	status[v]=finished;
  39. 	ftime[v]=++tme;
  40.  
  41. }
  42. void check_cl()
  43. {
  44. 	for(int i=0;i<n;i++)
  45. 	{
  46. 		for(int j=0;j<n;j++)
  47. 		{
  48. 			if(adj[i][j]==1)
  49. 			{
  50. 				if(dtime[i]<dtime[j])
  51. 				{
  52. 					int flag=0;
  53. 					for(int k=0;k<n;k++)
  54. 					{
  55. 						if(dtime[k]>=dtime[j]&&ftime[k]<=ftime[j])
  56. 						{
  57. 							for(int l=0;l<n;l++)
  58. 							{
  59. 								if(dtime[l]<=dtime[i]&&ftime[l]>=ftime[i])
  60. 								{
  61. 									if(be[k][l]==1)
  62. 									{
  63. 										flag=1;
  64. 									}
  65. 								}
  66. 							}
  67.  
  68. 						}
  69. 					}
  70. 					if(!flag)
  71. 					{
  72. 						cnt++;
  73. 						cl[i][j]=1;
  74. 					}
  75. 				}
  76. 			}
  77. 		}
  78. 	}
  79. }
  80. int main()
  81. { 
  82.     int v,e,x;
  83.     while(cin>>n)
  84.     {
  85.     	for(int i=0;i<max;i++)
  86.         {
  87.         	status[i]=0;
  88.         	dtime[i]=0;
  89.         	ftime[i]=0;
  90.         	for(int j=0;j<max;j++)
  91.         	{
  92.         		adj[i][j]=0;
  93.         		te[i][j]=0;
  94.         		be[i][j]=0;
  95.         		cl[i][j]=0;
  96.         	}
  97.         }
  98.     	tme=0;cnt=0;
  99.     	for (int i=0 ; i<n ; i++) {
  100.             scanf("%d (%d)",&v,&e);
  101.             for (int j=0 ; j<e ; j++) {
  102.                 scanf("%d",&x);
  103.                 adj[v][x]=1;
  104.                 adj[x][v]=1;
  105.  
  106.             }
  107.         }
  108.         for(int i=0;i<n;i++)
  109.         {
  110.         	if(status[i]==0)
  111.         	   dfs(i);
  112.         }
  113.         check_cl();
  114.         cout<<cnt<<" critical links"<<"\n";
  115.         for(int i=0;i<n;i++)
  116.         {
  117.         	for(int j=0;j<n;j++)
  118.         	{
  119.         		if(cl[i][j]==1)
  120.         		{
  121.         			cout<<i<<" - "<<j<<"\n";
  122.         		}
  123.         	}
  124.         }
  125.         cout<<"\n";
  126.     }
  127.     return 0;
  128. }
Success #stdin #stdout 0s 3928KB
comments (?)
stdin
copy 
2
0 (1) 1
1 (0) 0

1
0 (1) 1
stdout
copy 
1 critical links
0 - 1

0 critical links

0 critical links
https://ideone.com/rpPQdQ
language:
C++ (gcc 8.3)
created:
9 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!