kosarajo求强连通分量的证明
- 因为根据反向图的
dfs
求出的拓扑序列使得原本的dag
图中点的搜索优先级倒转 - 所以在原图
dfs
会优先将最末端的点优先跑完,而上面的点再跑时,因为下面的点已经被标记过,阻止了连通块的扩张,所以是正确的
例题
poj2186
题目链接
题意
n
个点m
条边,求有多少个点是任意点均可达到的
思路
- 根据反向图求出拓扑序列,再使用正向
dfs
求出连通分量,题目所求即第一个强连通分量中点的个数 - 注意:图本身可能是非联通的,要特判
代码
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int N = 10005;
vector<int> g[N], gr[N], path;
int vis[N], sscid[N], n, m;
void dfs1(int x) {
vis[x] = 1;
for(unsigned int i = 0; i < gr[x].size(); ++ i) {
int y = gr[x][i];
if(!vis[y]) {
dfs1(y);
}
}
path.push_back(x);
return;
}
void dfs2(int x, int cnt) {
sscid[x] = cnt;
for(unsigned int i = 0; i < g[x].size(); ++ i) {
int y = g[x][i];
if(!sscid[y]) {
dfs2(y, cnt);
}
}
return;
}
void dfs3(int x) {
vis[x] = 1;
for(unsigned int i = 0; i < gr[x].size(); ++ i) {
int y = gr[x][i];
if(!vis[y]) {
dfs3(y);
}
}
}
void kosarajo() {
int cnt = 0;
for(int i = 1; i <= n; ++ i) {
if(!vis[i]) {
dfs1(i);
}
}
reverse(path.begin(), path.end());
for(unsigned int i = 0; i < path.size(); ++ i) {
int x = path[i];
if(!sscid[x]) {
dfs2(x, ++ cnt);
}
}
}
void init() {
for(int i = 0; i < N; ++ i) {
g[i].clear();
gr[i].clear();
}
memset(vis, 0, sizeof(vis));
memset(sscid, 0, sizeof(sscid));
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
init();
for(int i = 1; i <= m; ++ i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
gr[v].push_back(u);
}
kosarajo();
int count = 0, x = 0;
for(int i = 1; i <= n; ++ i) {
if(sscid[i] == 1) {
++ count;
x = i;
}
}
memset(vis, 0, sizeof(vis));
dfs3(x);
bool flag = true;
for(int i = 1; i <= n; ++ i) {
if(!vis[i]) {
flag = false;
break;
}
}
if(!flag) cout << 0 << "\n";
else cout << count << "\n";
return 0;
}
标签:连通,gr,vis,kosarajo,int,include,求强
From: https://www.cnblogs.com/lemonsbiscuit/p/17084472.html