Tarjan

标签（空格分隔）： tarjan

kosaraju算法，comp with tarjan，复杂度差不多，写法较易，局限性较高

例题： popular cow

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define INF 99999999using namespace std;int n, m, cnt;int InNum[10005];//强连通分量的节点个数bool vis[10005];//判重int FaNam[10005];//节点隶属的强连通分量的编号vector
         
           e[10005];//正图vector
          
            re[10005];//反图vector
           
             s;//栈void dfs1(int x) { vis[x] = 1;//标记入栈 for(int i = 0; i < e[x].size(); i++) if(!vis[e[x][i]]) dfs1(e[x][i]);//扩展入栈节点 s.push_back(x);//入栈}void dfs2(int x) { FaNam[x] = cnt;//标记x隶属的强连通分量为cnt InNum[cnt]++;//编号为cnt的连通分量个数多一个 vis[x] = 1;//x已入强连通分量 for(int i = 0; i < re[x].size(); i++) if(!vis[re[x][i]]) dfs2(re[x][i]);//如果re[x][i]没有进入强连通分量}void Kosaraju() { memset(vis, 0, sizeof(vis)); for(int i = 1; i <= n; i++) { for(int j = 0; j < e[i].size(); j++) {//检查强连通分量的出度 int w = e[i][j]; if(FaNam[i] != FaNam[w]) vis[FaNam[i]] = 1;//设其为一 } } int ans; int t = 0; for(int i = 1; i <= cnt; i++) {//检查有几个强连通分量的出度为0 if(!vis[i]) { ans = i; t++; } } if(t == 1) //如有多个出度为零，显然不符合要求，不然就有编号为ans的强连通分量OK printf("%d\n", InNum[ans]); else printf("0\n");}int main() { int a, b; scanf("%d%d", &n, &m); for(int i = 0; i < m; i++) { scanf("%d%d", &a, &b); e[a].push_back(b); re[b].push_back(a); } for(int i = 1; i <= n; i++) if(!vis[i]) dfs1(i); memset(vis, 0, sizeof(vis)); memset(InNum, 0, sizeof(InNum)); cnt = 0; for(int i = s.size() - 1; i >= 0; i--) { if(!vis[s[i]]) { cnt++; dfs2(s[i]); } } Kosaraju(); return 0;}

tarjan算法

tarjan例图(最终版).png

| id | dfn | low |

| :--: | :-----: | :----: |

| 1 | 1 | 1 |

| 2 | 2 | 2 |

| 3 | 3 | 4 |

| 4 | 4 | 2 |

tarjan算法的中心逻辑：找环的key

术语补充
\(dfn\) : 这个节点在搜索树上
\(low\) : 这个节点隶属的强连通分量的\(key\)的\(dfn\)
\(key\) : 这个强连通分量中的节点第一次被外界访问的节点，如图中强连通分量\(\{2，3，4\}\)的\(key\)就是2
\(stack\) : 存储当前访问的节点（通常是一条路径或一段路径 注意区别）
\(scc\) : 强连通分量