tarjan 输出0 求调
查看原帖
tarjan 输出0 求调
848964
hzoi_Shadow楼主2023/7/15 16:50
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl '\n'
struct node
{
	int next,to;
}e[4000001];
vector<int>e_dcc[4000001];
stack<int>s;
int head[4000001],dfn[4000001],low[4000001],cnt=0,tot=0,ans=0;
void add(int u,int v)
{
	cnt++;
	e[cnt].next=head[u];
	e[cnt].to=v;
	head[u]=cnt;
}
void tarjan(int x,int fa)
{
    int i,k=0,pd=0;
    tot++;
    dfn[x]=low[x]=tot;
    s.push(x);
    for(i=head[x];i!=0;i=e[i].next)
    {
        if(dfn[e[i].to]==0)
        {
            tarjan(e[i].to,x);
            low[x]=min(low[x],low[e[i].to]);
            if(low[e[i].to]>dfn[x])
            {
                ans++;
                while(e[i].to!=k)
                {
                    k=s.top();
                    e_dcc[ans].push_back(k);
                    s.pop();
                }   
            }
        }
        else
        {
            if(e[i].to==fa&&pd==0)
            {
                pd=1;
            }
            else
            {
                low[x]=min(low[x],dfn[e[i].to]);
            }
        }
    }
}
int main()
{
	int n,m,i,j,u,v;
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		cin>>u>>v;
        if(u!=v)
        {
            add(u,v);
            add(v,u);
        }
	}
    for(i=1;i<=n;i++)
    {
        if(dfn[i]==0)
        {
            tarjan(i,i);
        }
    }
    cout<<ans<<endl;
    for(i=1;i<=ans;i++)
    {
        cout<<e_dcc[i].size()<<" ";
        for(j=0;j<e_dcc[i].size();j++)
        {
            cout<<e_dcc[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}·
2023/7/15 16:50
加载中...