求助
查看原帖
求助
549499
Disjoint_cat楼主2022/7/26 10:53

rt,样例4错了,WA 0

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=500005;
int n,m,u,v,low[N],dfn[N],idx,num;
bool vis[N];
vector<int>to[N],fl[N];
stack<int>st;
void tarjan(int id,int lst)
{
    low[id]=dfn[id]=++idx;
    st.push(id);
    vis[id]=1;
    for(int i=0;i<to[id].size();i++)
        if(!dfn[to[id][i]])
    	{
            tarjan(to[id][i],id);
        	low[id]=min(low[id],low[to[id][i]]);
			if(low[to[id][i]]>=dfn[id])
			{
				fl[++num].push_back(id);
				while(st.top()!=id)
					fl[num].push_back(st.top()),vis[st.top()]=0,\
					st.pop();
			}
       	}
        else if(to[id][i]!=lst)low[id]=min(low[id],dfn[to[id][i]]);
	if(to[id].size()==0)fl[++num].push_back(id);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
		if(u!=v)to[u].push_back(v),to[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])tarjan(i,0);
	printf("%d",num);
	for(int i=1;i<=num;i++)
	{
		printf("\n%d",fl[i].size());
		for(int j=0;j<fl[i].size();j++)printf(" %d",fl[i][j]);
	}
    return 0;
}
2022/7/26 10:53
加载中...