50pts求条!玄关
查看原帖
50pts求条!玄关
1069719
Enoch2013楼主2025/1/25 10:24

code:

#include <bits/stdc++.h>
#define N 2000005
using namespace std;
int pre[N], tot, dfn[N], low[N], st[N], top, cnt, deg_In[N], idx, n, m, root;
vector<int> vdcc[N];
struct node
{
	int to, ne;
} a[N << 1];
void add(int b, int e)
{
	a[tot] = (node){e, pre[b]};
	pre[b] = tot++;
	a[tot] = (node){b, pre[e]};
	pre[e] = tot++;
}
void tarjan(int u, int lst)
{
	int son = 0;
	dfn[u] = low[u] = ++cnt;
	st[++top] = u;
	for (int i = pre[u]; i; i = a[i].ne)
	{
		int to = a[i].to, vv;
		if (!dfn[to])
		{
			son++;
			tarjan(to, u);
			low[u] = min(low[u], low[to]);
			if (low[to] >= dfn[u])
			{
				idx++;
				vdcc[idx].push_back(u);
				++deg_In[u];
				do
				{
					vv = st[top--];
					vdcc[idx].push_back(vv);
					++deg_In[vv];
//					add(idx + n, vv);
				} while (vv != to);
			}
		}
		else if (to != (lst ^ 1))
			low[u] = min(low[u], dfn[to]);
	}
	if (u == root && son == 0)
		vdcc[++idx].push_back(u);
}
int main()
{
	cin >> n >> m;
	for (int i = 1, b, e; i <= m; i++)
	{
		cin >> b >> e;
		if (b == e)
			continue;
		add(b, e);
	}
	for (root = 1; root <= n; root++)
		if (!dfn[root])
		{
			tarjan(root, -1);
			top = 0;
		}
	int ans = 0;
	for (int i = 1; i <= n; i++)
		if (deg_In[i] > 1)
			ans++;
//	cout << ans << endl;
//	for (int i = 1, lst = 0; i <= n; i++)
//		if (deg_In[i] > 1)
//		{
//			if (lst)
//				cout << ' ';
//			lst = true;
//			cout << i;
//		}
//	putchar('\n');
	cout << idx << endl;
	for (int i = 1; i <= idx; i++)
	{
//		cout << i << endl;
		cout << vdcc[i].size() << ' ';
		for (auto j : vdcc[i])
			cout << j << ' ';
		cout << endl;
	}
	
	return 0;
}
2025/1/25 10:24
加载中...