Advertisement
Riz1Ahmed

Articulation Bridge

Feb 22nd, 2019
178
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.33 KB | None | 0 0
  1. ///Given a graph. Count the Articulation bridge
  2. #include <bits/stdc++.h>
  3. #define reset(x) memset(x,0,sizeof x)
  4. using namespace std;
  5. struct R{int l,r;};
  6. int c,dis[105];
  7. vector<int> adj[105];
  8. vector<R> ans;
  9. bool comp(R a,R b){
  10.     return a.l!=b.l ? a.l<b.l:a.r<b.r;
  11. }
  12. int ArtBridge(int p,int u){
  13.     if (dis[u]) return dis[u];
  14.     dis[u]=c++;
  15.     int f=dis[u],i;
  16.     for (i=0; i<adj[u].size(); i++){
  17.         int v=adj[u][i];
  18.         if (v==p) continue;
  19.         if (dis[v]) {f=min(f,dis[v]);continue;}
  20.         int x=ArtBridge(u,v);
  21.         if (x>dis[u]){
  22.             int x=u,y=v;
  23.             if (x>y) swap(x,y);
  24.             ans.push_back({x,y});
  25.         }
  26.         f=min(f,x);
  27.     }
  28.     return f;
  29. }
  30. int main(){
  31.     int i,j,n,u,x,v;
  32.     while (~scanf("%d",&n)){
  33.         for (i=0; i<104; i++) adj[i].clear();
  34.         reset(dis), ans.clear();
  35.         for (int h=0; h<n; h++){
  36.             scanf("%d (%d)",&u,&x);
  37.             for (i=0; i<x; i++)
  38.                 scanf("%d",&v),
  39.                 adj[u].push_back(v);
  40.         }
  41.         for (i=0,c=1; i<n; i++)
  42.             if (!dis[i]){
  43.                 dis[i]=c++;
  44.                 for (j=0; j<adj[i].size(); j++){
  45.                     u=i,v=adj[i][j];
  46.                     if (!dis[v]){
  47.                         int x=ArtBridge(u,v);
  48.                         if (x>dis[u]){
  49.                             if (u>v) swap(u,v);
  50.                             ans.push_back({u,v});
  51.                         }
  52.                     }
  53.                 }
  54.             }
  55.         sort(ans.begin(),ans.end(),comp);
  56.         printf("%d critical links\n",ans.size());
  57.         for (i=0; i<ans.size(); i++)
  58.             printf("%d - %d\n",ans[i].l,ans[i].r);
  59.         puts("");
  60.     }
  61.     return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement