Kosaraju 通过一次正向dfs和一次反向dfs求得强连通分量,时间复杂度O(M+N)

其中d[i]数组保存dfs1时第i个访问的节点,vis[i]保存第i个节点位于第k个强连通分量内,k<=n(全部不连通).

vector<int>sav[100002];
vector<int>sav_[100002];//反向图
int vis[100002],d[100002];
int u[50002],v[50002],t;//存边
int n,m;
int cnt[100002];//存储出/入度
void dfs1(int x){
    vis[x]=1;
    for(x的出边)
        if(!vis[v])
            dfs1(v)//不要写成dfs()
    d[++t]=x;//第t个访问x
}
void dfs2(int x){
    vis[x]=t;
    for(反向图中x的出边)
        if(!vis[v])
            dfs2(v);//不要写成dfs()
}
void Ko() {
	for(int i=1; i<=n; i++)
            if(!vis[i])dfs1(i);
	t=0;
	memset(vis,0,sizeof(vis));
	for(int i=n; i>=1; i--) {//反向遍历d[i]中的元素
		if(!vis[d[i]]) {
			t++;
			dfs2(d[i]);
		}
	}
}
void add(){
	x=read(),y=read();
	u[i]=x,v[i]=y;
	sav[x].push_back(y);
	sav_[y].push_back(x);
}

接下来是如何统计出(入)度

首先枚举每一条边 i ,如果其起点终点不在同一强连通分量中,则

cnt[vis[u[i]]]++(强连通分量出度)   cnt[vis[v[i]]]++(强连通分量入度)

for(int i=1; i<=m; i++) {
	if(vis[u[i]]!=vis[v[i]])cnt[vis[u[i]]]++;//v[i]
        //统计以u[i]或v[i]为成员的强连通分量出度/入度
}

对于出度为0的强连通分量,其不能到达任意其他强连通分量       对于入度为0的强连通分量,任意其他强连通分量均不能到达

Categories:

Tags:

No responses yet

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

近期评论
归档
分类