样例过了只对了一个点

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

henhen_ @ 2023-09-19 21:54:56

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,tot,tim;
int head[N],nxt[N],to[N],dfn[N],low[N];
bool vis[10010];
inline void add(int u,int v){
    to[++tot]=v;
    nxt[tot]=head[u];
    head[u]=tot;
}
int vis1[10010][10010];
stack<int>s;
int num[N],pos[N],cntt;
vector<int>q[N];
inline void tarjan(int x){
    dfn[x]=low[x]=++tim;
    s.push(x);
    vis[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }else if(vis[y]){
            low[x]=min(low[x],dfn[y]);
        }
    }
    if(low[x]==dfn[x]){
        ++cntt;
        //cout<<x<<endl;
        int now=s.top();
        //cout<<now<<" ";
        pos[x]=1;
        while(now!=x){
            q[x].push_back(now);
            s.pop();
            vis[now]=0;
            now=s.top();
            //cout<<now<<" ";
        }
        q[x].push_back(x);
        s.pop();
        vis[now]=0;
        //cout<<endl;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(x==y)continue;
        if(vis1[x][y])continue;
        add(x,y); 
        vis1[x][y]=1;
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    printf("%d\n",cntt);
    for(int i=1;i<=n;i++){
        if(pos[i]){
            sort(q[i].begin(),q[i].end());
            for(int j=0;j<q[i].size();j++){
                printf("%d ",q[i][j]);
            }
            printf("\n");
        }
    }
}

by 聊机 @ 2023-09-19 22:18:55

这么牛???还卷呢??


by hose @ 2023-09-25 21:01:19

这么牛???


|