0pts，样例3过不了，玄关

crzcqh @ 2024-12-28 10:46:25

#include<bits/stdc++.h>
using namespace std;
const int M=2e6+5;
const int N=2e5+5; 
int n,m,u,v,cnt=1,tot,ans;
int head[N],dfn[N],low[N],flag[M],c[M]; 
pair<int,int> edge[M];
map<pair<int,int>,int> f;
vector<int> eans[N];
void add(int u,int v){
    cnt++;
    edge[cnt].first=v;
    edge[cnt].second=head[u];
    head[u]=cnt;

}
void tarjan(int u,int l){
    dfn[u]=low[u]=++tot;
    for(int i=head[u];i;i=edge[i].second){
        v=edge[i].first;
        if(!dfn[v]){
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])
                flag[i]=flag[i^1]=1;            
        }else if(i!=(l^1))               
            low[u]=min(low[u],dfn[v]);
    }
}
void dfs(int u){
    c[u]=ans;
    eans[ans].push_back(u);
    for(int i=head[u];i;i=edge[i].second){
        v=edge[i].first;
        if(c[v]||flag[i])
            continue;
        dfs(v);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        if(f[make_pair(u,v)]==1) continue;
        add(u,v),add(v,u);
        f[make_pair(u,v)]=f[make_pair(v,u)]=1;
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i,0);
    for(int i=1;i<=n;i++)
        if(!c[i]){
            ans++,dfs(i);
        }
    cout<<ans<<endl;
    for(int i=1;i<=ans;i++){
        cout<<eans[i].size()<<' ';
        for(int v : eans[i]) cout<<v<<' ';
        cout<<endl;
    }
    return 0;
} 

by Herio @ 2024-12-28 12:26:49

把u,v改成局部变量：

#include<bits/stdc++.h>
using namespace std;
const int M=2e6+5;
const int N=2e5+5; 
int n,m,cnt=1,tot,ans;
int head[N],dfn[N],low[N],flag[M],c[M]; 
pair<int,int> edge[M];
map<pair<int,int>,int> f;
vector<int> eans[N];
void add(int u,int v){
    edge[++cnt].first=v;
    edge[cnt].second=head[u];
    head[u]=cnt;

}
void tarjan(int u,int l){
    dfn[u]=low[u]=++tot;
    for(int i=head[u];i;i=edge[i].second){
        int v=edge[i].first;
        if(!dfn[v]){
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])
                flag[i]=flag[i^1]=1;            
        }else if(i!=(l^1))    low[u]=min(low[u],dfn[v]);
    }
}
void dfs(int u){
    c[u]=ans;
    eans[ans].push_back(u);
    for(int i=head[u];i;i=edge[i].second){
        int v=edge[i].first;
        if(c[v]||flag[i])
            continue;
        dfs(v);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        //if(f[make_pair(u,v)]==1) continue;
        add(u,v),add(v,u);
        //f[make_pair(u,v)]=f[make_pair(v,u)]=1;
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i,0);
    for(int i=1;i<=n;i++)
        if(!c[i]){
            ans++,dfs(i);
        }
    cout<<ans<<endl;
    for(int i=1;i<=ans;i++){
        cout<<eans[i].size()<<' ';
        for(int v : eans[i]) cout<<v<<' ';
        cout<<endl;
    }
    return 0;
}