一种基于 vector 的做法

clx201022 @ 2024-01-05 21:04:34

by clx201022 @ 2024-01-05 21:12:05

#include<algorithm>
#include<vector>
#include<stack>
#include <cstdio>
struct node{int u, v;};
const int unreal_dfn=0;
void tarjan(std::vector<std::vector<int> > &ans,int &dfncnt,std::vector<int> &dfn,std::vector<int> &low,
std::vector<bool> &cut,std::stack<int> &s,const std::vector<int>e[],const int u,const int f)
{
    bool vis=false;//处理重边
    low[u]=dfn[u]=++dfncnt;
    s.push(u);
    for(auto v:e[u])
    {
        if(v==f)
        {
            //割边不像割点，割边的要求是 low[v]>dfn[u] 所以如果 访问上一个节点时回溯后 low[v] 将必定不大于 dfn[u]
            if(!vis)
            {
                vis=true;
                continue;
            }
        }//有重边那么就必不是割边，因为割了一条还有一条
        if(dfn[v]==unreal_dfn)//没有访问
        {
            tarjan(ans,dfncnt,dfn,low,cut,s,e,v,u);//dfn[v]>dfn[u]
            low[u]=std::min(low[u],low[v]);//这里可以是因为 dfn[v]>dfn[u] 所以 u 一定是 v 的上层 
        }
        else
            low[u]=std::min(low[u],dfn[v]);//不能和上面一样，因为可能有 dfn[u]>dfn[v]
    }
    if(dfn[u]==low[u])
    {
        std::vector<int>zzz;
        zzz.push_back(u);
        while(s.top()!=u)//不是 u
        {
            zzz.push_back(s.top());
            s.pop();
        }
        s.pop();//pop 掉 u
        ans.push_back(zzz);
    }
    return;
}/*dfncnt   记录当前已经访问了几个节点
dfn[ maxn ] 当前节点是第几个被访问到的
low[ maxn ] 当前节点不经过和父节点的连边（重边例外）所能访问到的最小的 dfn[ ]
cut[ maxn ] 节点是不是割点*/
using namespace std;
const int maxn=5e5;
std::vector<int>ans,e[maxn+1];
int main()
{
    int n=0,m=0;
    scanf("%d%d",&n,&m);
    for(int i=m,x,y;i>=1;i--)
    {
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    int dfncnt=unreal_dfn;
    std::vector<vector<int>> ans;
    std::vector<int> dfn(n+1,unreal_dfn),low(n+1,unreal_dfn);
    std::vector<bool> cut(n+1,false);
    std:stack<int>s;
    for(int i=1;i<=n;i++)
        if(dfn[i]==unreal_dfn)
            tarjan(ans,dfncnt,dfn,low,cut,s,e,i,i);//dfn[v]>dfn[u]
    printf("%d\n",ans.size());
    for(vector<int> zzz1:ans)
    {
        printf("%d ",(int)zzz1.size());
        for(int zzz2:zzz1)
        {
            printf("%d ",zzz2);
        }
        printf("\n");
    }
    return 0;
}

by CodingOIer @ 2024-03-27 15:17:21

by YakultGo @ 2024-04-02 16:21:15

厉害