1 条题解

  • 0
    @ 2026-6-20 20:28:31

    // eDCC缩点 Tarjan算法 O(n+m)
    #include<bits/stdc++.h>
    using namespace std;
    
    const int N=500010,M=4000010;
    int to[M],ne[M],h[N],idx=1; //2,3异或配对
    void add(int a,int b){
      to[++idx]=b,ne[idx]=h[a],h[a]=idx;
    }
    int n,m;
    int dfn[N],low[N],stk[N],top,cnt;
    // bool bri[M]; //标记桥
    vector<int> dcc[N]; //记录eDCC内的点
    
    void tarjan(int x,int e){
      dfn[x]=low[x]=++dfn[0]; stk[++top]=x;
      for(int i=h[x];i;i=ne[i]){
        int y=to[i];
        if(!dfn[y]){ //若y未访问
          tarjan(y,i);
          low[x]=min(low[x],low[y]);
          // if(low[y]>dfn[x]) bri[i]=bri[i^1]=1;
        }
        else if(i!=(e^1)) //若y已访问且不是反边
          low[x]=min(low[x],dfn[y]);
      }
      
      if(low[x]==dfn[x]){ //若x是edcc的根
        ++cnt;
        while(stk[top+1]!=x) dcc[cnt].push_back(stk[top--]);
      }
    }
    int main(){
      ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
      cin>>n>>m;
      for(int a,b;m--;)cin>>a>>b,add(a,b),add(b,a);
    
      for(int i=1;i<=n;i++)if(!dfn[i]) tarjan(i,0); //eDCC缩点
      
      cout<<cnt<<"\n";
      for(int i=1;i<=cnt;i++){ //枚举缩点
        cout<<dcc[i].size()<<" ";
        for(int j:dcc[i]) cout<<j<<" ";
        cout<<"\n";
      }
    }
    
    • 1

    信息

    ID
    12507
    时间
    2000ms
    内存
    600MiB
    难度
    10
    标签
    递交数
    3
    已通过
    3
    上传者