123456789101112131415161718192021222324252627282930313233343536 |
- #include<memory.h>
- struct edge{int e, nxt;};
- int V, E;
- edge e[MAXE], er[MAXE];
- int sp[MAXV], spr[MAXV];
- int group_cnt, group_num[MAXV];
- bool v[MAXV];
- int stk[MAXV];
- void fill_forward(int x)
- {
- int i;
- v[x]=true;
- for(i=sp[x];i;i=e[i].nxt) if(!v[e[i].e]) fill_forward(e[i].e);
- stk[++stk[0]]=x;
- }
- void fill_backward(int x)
- {
- int i;
- v[x]=false;
- group_num[x]=group_cnt;
- for(i=spr[x];i;i=er[i].nxt) if(v[er[i].e]) fill_backward(er[i].e);
- }
- void add_edge(int v1, int v2) //add edge v1->v2
- {
- e [++E].e=v2; e [E].nxt=sp [v1]; sp [v1]=E;
- er[ E].e=v1; er[E].nxt=spr[v2]; spr[v2]=E;
- }
- void SCC()
- {
- int i;
- stk[0]=0;
- memset(v, false, sizeof(v));
- for(i=1;i<=V;i++) if(!v[i]) fill_forward(i);
- group_cnt=0;
- for(i=stk[0];i>=1;i--) if(v[stk[i]]){group_cnt++; fill_backward(stk[i]);}
- }
|