92分求调
查看原帖
92分求调
470590
LikAzusa_楼主2023/11/16 08:06

WA on #11

//P3388 【模板】割点(割顶)

#include <bits/stdc++.h>

using namespace std;

inline int read()
{
	int x = 0, f = 1; char c = getchar();
	while(c > '9' || c < '0') {if(c == '-') f = -1; c = getchar();}
	while(c <= '9' && c >= '0') {x = x * 10 + c - '0'; c = getchar();}
	return x * f;
}

const int maxn = 1e5 + 10;
struct Node
{
	int u, v;
	int next;
}e[maxn << 1];
int n, m;
int dfn[maxn], low[maxn];
int h[maxn];
int vis[maxn];
int v[maxn];
int ap[maxn];
int ans;
int tot;
int cnt;

void addEdge(int u, int v)
{
	e[++tot].u = u;
	e[tot].v = v;
	e[tot].next = h[u];
	h[u] = tot;
}

void tarjan(int u, int fa)
{
	int ch = 0;//子树的数量
	dfn[u] = low[u] = ++cnt;
	for(int i = h[u]; i; i = e[i].next)
	{
		if(!dfn[e[i].v])
		{
			if(u == fa);
			tarjan(e[i].v, fa);
			low[u] = min(low[e[i].v], low[u]);
			if(u == fa && ch >= 2)
			{
				if(!v[u])
				{
					ap[++ans] = u;
					v[u] = 1;
				}
			}
			else if(u != fa && low[e[i].v] >= dfn[u])
			{
				if(!v[u])
				{
					ap[++ans] = u;
					v[u] = 1;
				}
			}
		}	
		low[u] = min(low[u], dfn[e[i].v]);	
	} 
}

int main()
{
	n = read(); m = read();
	for(int i = 1; i <= m; i++)
	{
		int u = read(), v = read();
		addEdge(u, v);
		addEdge(v, u);
	}
	for(int i = 1; i <= n; i++)
	{
		if(dfn[i] == 0) tarjan(i, i);
	}
	sort(ap + 1, ap + ans + 1);
	cout << ans << endl;
	for(int i = 1; i <= ans; i++)
	{
		cout << ap[i] << " ";
	}
	return 0;
}
2023/11/16 08:06
加载中...