Guest User

Untitled

a guest
Oct 17th, 2016
334
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.92 KB | None | 0 0
  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. }
Add Comment
Please, Sign In to add comment