#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=5e5+2;
int n,m;
vector<int>g1[N];
int dfn[N],low[N],dfn_tot=0;
stack<int>stk;
int belong[N],ebcc_tot=0;
vector<int>ebcc[N];
void Tarjan(int u,int fa)
{
    dfn[u]=low[u]=dfn_tot++;
    stk.push(u);
    bool flag=0;
    for(auto v:g1[u])
    {
    	if(v==u)continue;
    	if(!dfn[v])
    		Tarjan(v,u),low[u]=min(low[u],low[v]);
    	else if(v!=fa || flag)
    		low[u]=min(low[u],dfn[v]);
    	else flag=1;
	}
	if(dfn[u]==low[u])
	{
		ebcc_tot++;
		int v;
		do
		{
			v=stk.top(),stk.pop();
			belong[v]=ebcc_tot;
			ebcc[ebcc_tot].push_back(v);
		}while(u!=v);
	}
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;cin>>a>>b;
        g1[a].push_back(b);
        g1[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])Tarjan(i,0);
    cout<<ebcc_tot<<"\n";
    for(int i=1;i<=ebcc_tot;i++,cout<<"\n")
    {
    	cout<<ebcc[i].size()<<" ";
    	for(auto j:ebcc[i])
    		cout<<j<<" ";
	}
    return 0;
}

0 comments

No comments so far...

Information

ID
415
Time
1000ms
Memory
256MiB
Difficulty
7
Tags
# Submissions
60
Accepted
14
Uploaded By