fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define MAX 105
  5.  
  6.  
  7. int dtime;
  8. set< pair< int,int > > artiPnt;
  9. vector< int > graph[MAX];
  10. int d[MAX],vis[MAX],low[MAX],edge[MAX][MAX];
  11.  
  12. void artiPoint(int s, int par=-1){
  13.     dtime++;
  14.     d[s]=low[s]=dtime;
  15.     vis[s]=1;
  16.     int u=s;
  17.     for(int i=0;i<graph[u].size();i++){
  18.         int v = graph[u][i];
  19.         edge[u][v]++;
  20.         if(v==par)
  21.             continue;
  22.  
  23.         if(!vis[v]){
  24.             artiPoint(v,u);
  25.             low[u]=min(low[v],low[u]);
  26.  
  27.             if(d[u]<low[v] && edge[v][u]==1){
  28.                 artiPnt.insert({min(u,v),max(u,v)});
  29.             }
  30.         } else{
  31.             low[u]=min(low[u],d[v]);
  32.         }
  33.     }
  34. }
  35.  
  36.  
  37. int main(){
  38.     int n;
  39.     while(cin>>n){
  40.         for(int i=0;i<MAX;i++) graph[i].clear();
  41.         artiPnt.clear();
  42.         for(int i=1;i<=n;i++){
  43.             int src;
  44.             cin>>src;
  45.             getchar();
  46.             getchar();
  47.             int m; cin>>m;
  48.             getchar();
  49.             getchar();
  50.             //cout<<m;
  51.             for(int j=1;j<=m;j++){
  52.                 int dest;
  53.                 cin>>dest;
  54.                 graph[src].pb(dest);
  55.                 //graph[dest].pb(src);
  56.             }
  57.         }
  58.  
  59.         memset(vis,0,sizeof vis);
  60.         memset(d,0,sizeof d);
  61.         memset(low,0,sizeof low);
  62.         memset(edge,0,sizeof edge);
  63.         dtime=0;
  64.         for(int i=0;i<n;i++){
  65.             if(!vis[i])
  66.                 artiPoint(i);
  67.         }
  68.  
  69.         cout<<artiPnt.size()<<" critical links\n";
  70.         for(auto i = artiPnt.begin();i!=artiPnt.end();i++){
  71.             cout<<i->first<<" - "<<i->second<<endl;
  72.         }
  73.         cout<<endl;
  74.     }
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0s 15288KB
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 (3) 1 2 4
1 (3) 0 2 3
2 (3) 1 0 3
3 (4) 0 1 2 4
4 (3) 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

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