Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ///Given a graph. Count the Articulation bridge
- #include <bits/stdc++.h>
- #define reset(x) memset(x,0,sizeof x)
- using namespace std;
- struct R{int l,r;};
- int c,dis[105];
- vector<int> adj[105];
- vector<R> ans;
- bool comp(R a,R b){
- return a.l!=b.l ? a.l<b.l:a.r<b.r;
- }
- int ArtBridge(int p,int u){
- if (dis[u]) return dis[u];
- dis[u]=c++;
- int f=dis[u],i;
- for (i=0; i<adj[u].size(); i++){
- int v=adj[u][i];
- if (v==p) continue;
- if (dis[v]) {f=min(f,dis[v]);continue;}
- int x=ArtBridge(u,v);
- if (x>dis[u]){
- int x=u,y=v;
- if (x>y) swap(x,y);
- ans.push_back({x,y});
- }
- f=min(f,x);
- }
- return f;
- }
- int main(){
- int i,j,n,u,x,v;
- while (~scanf("%d",&n)){
- for (i=0; i<104; i++) adj[i].clear();
- reset(dis), ans.clear();
- for (int h=0; h<n; h++){
- scanf("%d (%d)",&u,&x);
- for (i=0; i<x; i++)
- scanf("%d",&v),
- adj[u].push_back(v);
- }
- for (i=0,c=1; i<n; i++)
- if (!dis[i]){
- dis[i]=c++;
- for (j=0; j<adj[i].size(); j++){
- u=i,v=adj[i][j];
- if (!dis[v]){
- int x=ArtBridge(u,v);
- if (x>dis[u]){
- if (u>v) swap(u,v);
- ans.push_back({u,v});
- }
- }
- }
- }
- sort(ans.begin(),ans.end(),comp);
- printf("%d critical links\n",ans.size());
- for (i=0; i<ans.size(); i++)
- printf("%d - %d\n",ans[i].l,ans[i].r);
- puts("");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement