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]为成员的强连通分量出度/入度
}
No responses yet