警示后人:处理重边是如果用mapsubtask4会超时:

P8436 【模板】边双连通分量

myj128128 @ 2024-11-26 19:35:30

提供一个vector模拟map的写法

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
int read(){
    int m=0;int f=1;char c=getchar();
    while((c<'0'||c>'9')){if(c=='-')f=-1;c=getchar();}
    while(!(c<'0'||c>'9')){m=m*10+(c-'0');c=getchar();}
    return m*f;
}
const int maxn=500050;
int n,m;
vector<int>vec[maxn];
int low[maxn];
int dfn[maxn];
int tot;
int ecc;
vector<bool>bridge[maxn];
vector<pii >mp[maxn];
void tarjan(int u,int fa){
    low[u]=dfn[u]=++tot;
    for(int i=0;i<vec[u].size();i++){
        int v=vec[u][i];
        if(v==fa)continue ;
        if(!dfn[v]){
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]){
                ecc++;
//              bridge.pb({min(u,v),max(u,v)});
                bridge[u][i]=bridge[mp[u][i].first][mp[u][i].second]=1;
            }
        }else low[u]=min(low[u],dfn[v]);
    }
}
int col[maxn];
vector<int >ans[maxn];
int cnt;
void dfs(int u){
    col[u]=cnt;
    ans[cnt].pb(u);
    for(int i=0;i<vec[u].size();i++){
        int v=vec[u][i];
        if(bridge[u][i]||col[v])continue ;
        dfs(v);
    }
}
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    n=read();
    m=read();
    for(int i=1;i<=m;i++){
        int u;int v;
        u=read();v=read();
        vec[u].pb(v);
        vec[v].pb(u);
        bridge[u].pb(0);
        bridge[v].pb(0);
//      mp[{u,vec[u].size()-1}]={v,vec[v].size()-1};
//      mp[{v,vec[v].size()-1}]={u,vec[u].size()-1};
        mp[u].pb({v,vec[v].size()-1});
        mp[v].pb({u,vec[u].size()-1});
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjan(i,0);
        }
    }
//  for(int i=1;i<=n;i++){
//      for(int j=0;j<vec[i].size();j++){
//          int v=vec[i][j];
//          if(mp[{i,v}])bridge[i][j]=1;
//      }
//  }
    for(int i=1;i<=n;i++){
        if(!col[i]){
            ++cnt;
            dfs(i);
        }
    }
//  for(int i=1;i<=cnt;i++)
//      sort(ans[i].begin(),ans[i].end());
    cout<<cnt<<'\n';
    for(int i=1;i<=cnt;i++){
        cout<<ans[i].size()<<' ';
        for(int u:ans[i])cout<<u<<' ';
        cout<<'\n';
    }
    return 0;
}

|