一道简单的入门题
  • 板块学术版
  • 楼主不慕放糖
  • 当前回复5
  • 已保存回复5
  • 发布时间2021/10/28 21:17
  • 上次更新2023/11/4 02:02:45
查看原帖
一道简单的入门题
544113
不慕放糖楼主2021/10/28 21:17

这是一段用kosaraju求强连通分量的代码

#include<bits/stdc++.h>
using namespace std;
vector<int>e[10000];
vector<int>ef[10000];
vector<int>s;
int vis[10000],color[10000],sccnt;  
vector<int> ans[10010];
int n,m;//n个点m条边;
void dfs1(int u){
    if(vis[u]) return;
    vis[u]=true;
    for(int i=0;i<e[u].size();i++){
        if(!vis[e[u][i]]) dfs1(e[u][i]);
    }
    s.push_back(u);//人栈 
} //dsf1遍历的是正图的遍历顺序,按顺序入栈. 
void dfs2(int u) {
  color[u] = sccnt;
  for (int v : ef[u])
    if (!color[v]) dfs2(v);
}//dfs2选择最后遍历的节点,将他们成为同一颜色 
void kosaraju() {
  sccnt = 0;//初始化scc的个数为0 
  for (int i = 1; i <= n; ++i)
    if (!vis[i]) dfs1(i);//如果没有遍历则遍历之 
  for (int i = n-1; i >= 0; --i)//s总共只有n个,vector是从0开始的, dfs2从最晚的节点开始选 
    if (!color[s[i]]) {//而且当前节点这个点有颜色 
      ++sccnt; //联通分量的个数++ 
      dfs2(s[i]);//将这个点能链接变色 
    }
}
int main(){

    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        e[x].push_back(y);//正图;
        ef[y].push_back(x);// 反图; 
    } 
    kosaraju();
    for ( int i=1 ; i<=n ; i++ )
        ans[color[i]].push_back(i);
    for ( int i=1 ; i<=sccnt ; i++ ){
        cout<<"第"<<i<<"个scc包含:";
        for ( int j=0 ; j<ans[i].size() ; j++ )
            cout<<ans[i][j]<<' ';
        cout<<" 共"<<ans[i].size()<<"个"<<endl;
    }
    return 0;
}

求助:

if (!color[v]) dfs2(v);

if (!color[s[i]])

这两行代码什么意思?

2021/10/28 21:17
加载中...