图的强连通求解

->Kosaraju算法

    1.对原图G进行深度优先遍历，记录每个点的离开时间放入栈中。

    2.选栈顶元素，对反图GT进行遍历，删除能够遍历到的点，这些点构成一个强连通分量。

    3.若还有顶点没有被删除，循环 步骤2，否则算法结束

#include<bits/stdc++.h> using namespace std; int n,m,s; int stak[10010],top; vector<int> edge[10010],edge_T[10010]; //原图与反图 bool vis[10010]; //判断该点是否遍历过 void DFS_O(int v) { vis[v] = true; for(int i=0; i<edge[v].size(); i++) { if(!vis[edge[v][i]]) { DFS_O(edge[v][i]); } } stak[top++] = v; } void DFS_T(int v) { vis[v] = true; for(int i=0; i<edge_T[v].size(); i++) { if(!vis[edge_T[v][i]]) { DFS_T(edge_T[v][i]); } } } int Kosarajo() { int cnt=0; top = 0; memset(vis,false,sizeof(vis)); //这样写也可以 memset(vis,false,sizeof vis); for(int i=1; i<=n; i++) if(!vis[i]) DFS_O(i); memset(vis,false,sizeof(vis)); while(top>0) { s = stak[--top]; if(!vis[s]) { DFS_T(s); ++cnt;//强联通连通分支数+1 } } return cnt; } int main() { int a,b; while(scanf("%d%d",&n,&m)) { if(n==0&&n==0) break; for(int i=1;i<=n;++i) { edge[i].clear(); edge_T[i].clear(); } for(int i=0;i<m;i++) { scanf("%d%d",&a,&b); edge[a].push_back(b); edge_T[b].push_back(a); } printf("%s\n",Kosarajo()==1?"Yes":"No"); } return 0; }

->Tarjan算法

    1.找一个未被访问过的点v，若没有算法结束。

    2.初始化dfn[v]和low[v]

        对于v的所有邻接顶点u：

            ①未访问过，回到 步骤2，同时维护low[v];

            ②访问过但未删除，维护low[v].

            当low[v]==dfn[v]时 输出相应强连通分量。               

#include<bits/stdc++.h> using namespace std; #define ll long long #define M 10010 int n,m; vector<int> edge[M]; int cnt;//强连通分量个数 int top; int Index; int dfn[M],low[M];// dfn[v]表示顶点v被访问的时间 low[v]与顶点v邻接的未删除的顶点u的low[v]和low[u]的最小值 int stak[M],Belong[M];//Belong[]为每个结点所对应的强连通分量标号数组 bool Instak[M]; void Init() { cnt = top = Index = 0; for(int i=1;i<=n;i++) low[i] = dfn[i] = 0; } void Tarjan(int u) { stak[top++] = u; Instak[u] = 1; low[u] = dfn[u] = ++Index; for(int i=0;i<edge[u].size();i++) { int v = edge[u][i]; if(!dfn[v]) { Tarjan(v); low[u] = min(low[v],low[u]); } else if(Instak[v]) low[u] = min(low[u],dfn[v]); } if(low[u] == dfn[u]) { ++cnt; int v; do{ v = stak[--top]; Instak[v] = 0; Belong[v] = cnt; }while(u!=v); } } int main() { while(scanf("%d%d",&n,&m)&&(m+n)) { for(int i=1;i<=n;i++) edge[i].clear(); while(m--) { int x,y; scanf("%d%d",&x,&y); edge[x].push_back(y); } Init(); for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i); printf("%s\n",cnt==1?"Yes":"No"); } return 0; }