Tarjan求强连通分量模板

 1 inline void tarjan(int x) {
 2     int v;
 3     dfn[x] = low[x] = ++sum;
 4     a.push(x);
 5     _in[x] = 1;
 6     for(int i = head[x];i != -1; i = e[i].next) {
 7         v = e[i].to;
 8         if(!dfn[v]) {
 9             tarjan(v);
10             low[x] = min(low[x],low[v]); 
11         }
12         else if(_in[v]) 
13             low[x] = min(low[x],dfn[v]);
14     }
15     if(dfn[x] == low[x]) {
16         csp++;
17         do {
18             v = a.top();
19             a.pop();
20             _in[v] = false;
21             num[csp]++;
22             belong[v] = csp; 
23         }
24         while(v != x);
25     }
26 }

 

上一篇:Bug驱动开发(Bug-driven development)


下一篇:Android应用程序启动过程(二)分析