强连通分量——两次DFS求解

两次DFS求解"/>

强连通分量——两次DFS求解

\quad 求一个有向图强连通分量个数以及每个点所属连通分量

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;const int maxn = 1e5+10;
vector<int> E[maxn];  // 正向边
vector<int> rE[maxn]; // 反向边
vector<int> a;  // 后序遍历图记录下顶点遍历顺序
int vis[maxn];
int cmp[maxn];  // 记录每个顶点所属连通分量编号void dfs(int u)
{vis[u] = 1;for(int i = 0; i < E[u].size(); i++){int v = E[u][i];if(vis[v]==0) dfs(v);}a.push_back(u);
}void rdfs(int u, int k)
{vis[u] = 1;cmp[u] = k;for(int i = 0; i < rE[u].size(); i++){int v = rE[u][i];if(vis[v]==0) rdfs(v, k);}
}
// 返回连通分量个数
int scc(int n)
{memset(vis, 0, sizeof(vis));for(int i = 1; i <= n; i++)if(vis[i]==0) dfs(i);memset(vis, 0, sizeof(vis));int k = 0;for(int i = a.size()-1; i >= 0; i--)if(vis[a[i]]==0) rdfs(a[i], k++);return k;
}
int main()
{int n, m; cin >> n >> m;while(m--){int u, v; cin >> u >> v;E[u].push_back(v);rE[v].push_back(u);}int res = scc(n);cout << res << endl;return 0;
}/*
输入
6 10
1 2
2 3
3 1
2 4
4 5
4 6
5 6
5 7
6 5
6 7
*/