1 条题解

  • 0
    @ 2026-6-20 21:45:53

    #include<bits/stdc++.h>
    using namespace std;
    
    const int N=500010;
    int n,m;
    int dfn[N],low[N],stk[N],top,cnt,root,cut[N];
    vector<int> e[N],dcc[N];
    
    void tarjan(int x){
      dfn[x]=low[x]=++dfn[0]; stk[++top]=x;
      
      if(x==root&&!e[x].size()){ //孤立点
        dcc[++cnt].push_back(x);
        return;
      }
      int son=0;
      for(int y:e[x]){
        if(!dfn[y]){ //若y未访问
          tarjan(y);
          low[x]=min(low[x],low[y]);
          
          if(low[y]>=dfn[x]){ //x是割顶
            son++;
            if(x!=root||son>1)cut[x]=1; //记录割点
            
            // 每次回到割顶时记录vDCC
            ++cnt;
            for(int z=-1;z!=y;){ //让x留在栈中
              z=stk[top--];
              dcc[cnt].push_back(z);
            }
            dcc[cnt].push_back(x); //记录vDCC
          }
        }
        else //若y已访问
          low[x]=min(low[x],dfn[y]);
      }
    }
    int main(){
      ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
      cin>>n>>m;
      for(int a,b;m--;){
        cin>>a>>b;
        if(a==b) continue; //忽略自环
        e[a].push_back(b),
        e[b].push_back(a);
      }
      
      for(root=1;root<=n;root++)if(!dfn[root])tarjan(root);
      
      cout<<cnt<<"\n";
      for(int i=1;i<=cnt;i++){
        cout<<dcc[i].size()<<" ";
        for(int j:dcc[i])cout<<j<<" ";
        cout<<"\n";
      }
    }
    

    #include<bits/stdc++.h>
    using namespace std;
    
    const int N=10010;
    int n,m,a,b;
    vector<int> e[N],ne[N],dcc[N];
    int dfn[N],low[N],tot,stk[N],top,cut[N],root,cnt;
    int id[N];
    
    void tarjan(int x){
      dfn[x]=low[x]=++tot;
      stk[++top]=x;
      if(x==root&&!e[x].size()){ //孤立点
        dcc[++cnt].push_back(x);
        return;
      }
      int son=0;
      for(int y:e[x]){
        if(!dfn[y]){ //若y未访问
          tarjan(y);
          low[x]=min(low[x],low[y]); 
          if(low[y]>=dfn[x]){
            son++;
            if(x!=root||son>1)cut[x]=1; //割点
            
            ++cnt;
            while(1){
              int z=stk[top--];
              dcc[cnt].push_back(z);
              if(z==y) break; //让x留在栈中
            }
            dcc[cnt].push_back(x); //vDCC
          }
        }
        else //若y已访问
          low[x]=min(low[x],dfn[y]);
      }
    }
    int main(){
      cin>>n>>m;
      while(m--){
        cin>>a>>b;
        e[a].push_back(b),
        e[b].push_back(a);
      }
      for(root=1;root<=n;root++)if(!dfn[root])tarjan(root);
          
      //给每个割点一个新编号(cnt+1开始)
      int num=cnt;
      for(int i=1;i<=n;i++)if(cut[i])id[i]=++num;
      //建树,从每个缩点向对应割点连边
      for(int i=1;i<=cnt;i++){
        for(int j=0;j<dcc[i].size();j++){
          int x=dcc[i][j];
          if(cut[x]){
            ne[i].push_back(id[x]),
            ne[id[x]].push_back(i);        
          }
        }
      }
    }
    
    • 1

    D19【模板】vDCC 缩点 Tarjan 算法【模板】点双连通分量

    信息

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