# Untitled

a guest
Oct 17th, 2016
108
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /***************** NEW ******************/
2. VI tree[N],g[N];//edge list representation of graph
3. int U[M],V[M],vis[N],arr[N],T,cmpno,dsu[N];
4. bool isbridge[M]; // if i'th edge is a bridge edge or not
5. int adj(int u,int e){
6.   return U[e]^V[e]^u;
7. }
8. int f(int x){
9.   return dsu[x]=(dsu[x]==x?x:f(dsu[x]));
10. }
11. void merge(int a,int b){
12.   a=f(a);b=f(b);
13.   dsu[a]=b;
14. }
15. int dfs0(int u,int edge){ //mark bridges
16.   vis[u]=1;arr[u]=T++;
17.   int dbe = arr[u];
18.   for(auto e : g[u]){
19.     int w = adj(u,e);
20.     if(!vis[w])dbe = min(dbe,dfs0(w,e));
21.     else if(e!=edge)dbe = min(dbe,arr[w]);
22.   }
23.   if(dbe == arr[u] && edge!=-1)isbridge[edge]=true;
24.   else if(edge!=-1)merge(U[edge],V[edge]);
25.   return dbe;
26. }
27. void buildBridgeTree(int n){
28.   for(int i=1;i<=n;i++)dsu[i]=i;
29.   for(int i=1;i<=n;i++)if(!vis[i])dfs0(i,-1);
30.   for(int i=1;i<=m;i++)
31.     if(f(U[i])!=f(V[i]))
32.       tree[f(U[i])].PB(f(V[i])),
33.         tree[(f(V[i])].PB(U[i]);
34. }
RAW Paste Data