0pts求调
查看原帖
0pts求调
667558
_Kamisato_Ayaka_楼主2024/11/12 16:58
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e6 + 10;
int n,m,idx = 1,head[MAXN << 1],cur;
int low[MAXN],dfn[MAXN],color[MAXN],sccnt;
bool vis[MAXN];
stack < int > st;
vector < int > Ans[MAXN];
struct node{
	int v,nxt;
}edge[MAXN << 1];
inline void add(int u,int v)
{
	edge[idx].v = v;
	edge[idx].nxt = head[u];
	head[u] = idx ++;
}
inline void tarjan(int u,int fa)
{
	low[u] = dfn[u] = ++ cur;
	vis[u] = 1;
	st.push(u);
	for(int i = head[u];i != -1;i = edge[i].nxt)
	{
		int v = edge[i].v;
		if(i == (fa ^ 1)) continue;
		if(!dfn[v])
		{
			tarjan(v,i);
			low[u] = min(low[u],low[v]);
		}
		else if(vis[v])
			low[u] = min(low[u],dfn[v]);
	}
	if(dfn[u] == low[u])
	{
		sccnt ++;
		while(st.top() != u)
		{
			color[st.top()] = sccnt;
			vis[st.top()] = 0;
			Ans[sccnt].push_back(tmp);
			st.pop();
		}
		st.pop();
	}
}
signed main()
{
	cin.tie(0) -> sync_with_stdio(0);
	cout.tie(0) -> sync_with_stdio(0);
	cin >> n >> m;
	memset(head,-1,sizeof(head));
	for(int i = 1;i <= m;i ++)
	{
		int u,v;
		cin >> u >> v;
		if(u != v) add(u,v),add(v,u);
	}
	for(int i = 1;i <= n;i ++)
	{
		if(!dfn[i]) tarjan(i,0);
	}
	cout << sccnt << endl;
	for(int i = 1;i <= sccnt;i ++)
	{
		cout << Ans[i].size() << " ";
		for(int j = 0;j < Ans[i].size();j ++)
			cout << Ans[i][j] << " ";
		cout << endl;
	}
	return 0;
}
2024/11/12 16:58
加载中...