kasarujo求调

B3609 [图论与代数结构 701] 强连通分量

GODTREE @ 2024-03-24 11:41:13

re了

#include <bits/stdc++.h>
#define N 50005
using namespace std;
struct edge
{
    int nxt,to;
}e[N],fe[N];
int n,m,head[N],cnt,s[N],fcnt,od[N],fhead[N];
vector<int> scc[N];
bool vis[N];
void add(int u,int v)
{
    e[++cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].to=v;
}
void fadd(int u,int v)
{
    fe[++fcnt].nxt=fhead[u];
    fhead[u]=fcnt;
    fe[fcnt].to=v;
}
void dfs1(int u)
{
    vis[u]=1;
    for (int i=head[u];i!=0;i=e[i].nxt)
    {
        int v=e[i].to;
        if(vis[v]==0)
        {
            dfs1(v);
        }
    }
    s[++cnt]=u;
}
void dfs2(int u)
{
    vis[u]=1;
    for (int i=fhead[u];i!=0;i=fe[i].nxt)
    {
        int v=fe[i].to;
        if(vis[v]==0)
        {
            dfs2(v);
        }
    }
    scc[cnt].push_back(u);
}
int main()
{
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
        fadd(y,x);
    }
    cnt=0;
    dfs1(1);
    memset(vis,0,sizeof(vis));
    cnt=0;
    for (int i=n;i>=1;i--)
    {
        if (vis[s[i]]==0)
        {
            dfs2(s[i]);
            od[s[i]]=cnt;
        }
        cnt++;
    }
    for (int i=1;i<=n;i++)
    {
        sort(scc[i].begin(),scc[i].end());
    }
    for (int i=1;i<=n;i++)
    {
        if(vis[i]==0)
        {
            for (int j=0;j<scc[i].size();j++)
            {
                cout<<scc[i][j]<<" ";
            }
        }
        cout<<"\n";
    }
    return 0;
}

by __My0217__ @ 2024-03-24 12:18:20

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#define N 10005
using namespace std;
vector<int> G[N];
vector<int> _G[N];
vector<int> ans[N];
int vis[N], h[N], tot, cnt, _vis[N];
void dfs1(int u){
    vis[u] = 1;
    for(int i = 0 ; i < G[u].size() ; i++){
        int to = G[u][i];
        if(vis[to]) continue;
        dfs1(to);
    }
    h[++tot] = u;
}
void dfs2(int u, int k){
    vis[u] = k;
    ans[k].push_back(u);
    for(int i = 0 ; i < _G[u].size() ; i++){
        int to = _G[u][i];
        if(vis[to]) continue;
        dfs2(to, k);
    }
}
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1 ; i <= m ; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        _G[v].push_back(u);
    }
    //puts("Ok");
    for(int i = 1 ; i <= n ; i++){
        if(vis[i]) continue;
        dfs1(i);
    } 
    //puts("Ok");
    memset(vis, 0, sizeof(vis));
    for(int i = tot ; i >= 1 ; i--){
        if(vis[h[i]]) continue;
        dfs2(h[i], ++cnt);
    }
    for(int i = 1 ; i <= cnt ; i++){
        sort(ans[i].begin(), ans[i].end());
    }
    printf("%d\n", cnt);
    for(int i = 1 ; i <= n ; i++){
        int now = vis[i];
        if(_vis[now]) continue;
        _vis[now] = 1;
        for(int j = 0 ; j < ans[now].size() ; j++){
            printf("%d ", ans[now][j]);
        } puts("");
    }
    return 0;
}

|