关于kosarju算法代码求助
  • 板块灌水区
  • 楼主不慕放糖
  • 当前回复9
  • 已保存回复9
  • 发布时间2021/10/26 19:18
  • 上次更新2023/11/4 02:12:05
查看原帖
关于kosarju算法代码求助
544113
不慕放糖楼主2021/10/26 19:18
#include<bits/stdc++.h>
using namespace std;
vector<int>e[10000];
vector<int>ef[10000];
vector<int>s;
int vis[10000],color[10000],sccnt;  
int n,m;//n个点m条边;
void dfs1(int u){
    if(vis[u]) return;
    for(int i=0;i<e[u].size();i++){
        if(!vis[e[u][i]]) dfs1(e[u][i]);
    }
    s.push_back(u);//人栈 
} 
void dfs2(int u) {
  color[u] = sccnt;
  for (int v : ef[u])
    if (!color[v]) dfs2(v);
}

void kosaraju() {
  sccnt = 0;
  for (int i = 1; i <= n; ++i)
    if (!vis[i]) dfs1(i);
  for (int i = n; i >= 1; --i)
    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<=1)
    return 0;
}
/*
6 8
1 3
3 5
5 6
4 6
2 4
1 2
4 1
3 4
*/

不知道怎么输出?sccnt是什么意思?

for (int v : ef[u])
2021/10/26 19:18
加载中...