割点模板28pts求助, WA8个RE1个
查看原帖
割点模板28pts求助, WA8个RE1个
158652
IQ勇士楼主2022/12/14 17:54
#include<iostream>
#include<cstdio>
using namespace std;
struct edge{
	int to;
	int nxt;
}e[200001];
int cnt, dfn[10001], low[10001], head[10001], timec, n, m, u, v, root, sum;
bool isgd[10001];
void add(int uu, int vv)
{
	e[++cnt].to = vv;
	e[cnt].nxt = head[uu];
	head[uu] = cnt;
}
void dfs(int now, int fa)
{
	int child = 0;	
	dfn[now] = ++timec;
	low[now] = timec;
	for(int i = head[now]; i; i = e[i].nxt)
	{
		if(!dfn[e[i].to])
		{
			child++;
			dfs(e[i].to, now);
			low[now] = min(low[now], low[e[i].to]);
			if(low[e[i].to] >= dfn[now] && now != root)
			{
				if(isgd[now] == 0)
					sum++;
				isgd[now] = 1;
			}
			if(now == root && child >= 2)
			{
				if(isgd[now] == 0)
					sum++;
				isgd[now] = 1;
			}
		}
		else if(e[i].to != fa)
			low[now] = min(low[now], dfn[e[i].to]);
	}
}
int main()
{
	freopen("s.in", "r", stdin);
	freopen("s.out", "w", stdout);
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		cin >> u >> v;
		add(u, v);
		add(v, u);
	}
	for(int i = 1; i <= n; i++)
	{
		if(!dfn[i])
		{
			root = i;
			dfs(i, root);
		}
	}
	cout << sum << endl;
	for(int i = 1; i <= n; i++)
		if(isgd[i])
			cout << i << ' ';
	return 0;
}
2022/12/14 17:54
加载中...