萌新刚学OI,Tarjan 24pts 求助
查看原帖
萌新刚学OI,Tarjan 24pts 求助
262147
Reobrok_Kk楼主2021/6/24 14:35
#include <bits/stdc++.h>
using namespace std;
inline void read(int &x) {
	bool flag = 1;
	char c = getchar();
	while (!isalnum(c)) {
		if (c == '-')
		  flag = 0;
		c = getchar();
	}
	x = c - '0';
	c = getchar();
	while (isalnum(c)) {
		x = (x << 1) + (x << 3) + c - '0';
		c = getchar();
	}
	if (!flag) x = ~(x - 1);
}
inline void write(int x) {
	if (x < 0) {
		putchar('-');
		x = ~(x - 1);
	}
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}
const int N = 2e4 + 5, M = 2e5 + 5;
struct Edge {
	int front, to, nxt;
}e[M];
bool flag[N], vis[N];
int head[N], tot, root;
int dfn[N], low[N], num;
int answer, ans[N];
void add(int x, int y) {
	e[++tot].to = y;
	e[tot].front = x;
	e[tot].nxt = head[x];
	head[x] = tot;
}
void Tarjan(int x, int fa) {
	dfn[x] = low[x] = ++num;
	vis[x] = true;
	int child = 0;
	for (int i = head[x]; i; i = e[i].nxt) {
		int y = e[i].to;
		if (!vis[y]) {
			child++;
			Tarjan(y, x);
			low[x] = min(low[x], low[y]);
			if (x != root && low[x] > dfn[fa] && !flag[x]) {
				flag[x] = true;
				answer++;
				ans[answer] = x;
			}
		}
		else if (y != fa)
		low[x] = min(low[x], dfn[y]);
	}
	if (x == root && child >= 2 && !flag[x]) {
		flag[x] = true;
		answer++;
		ans[answer] = x;
	}
}
signed main() {
	int n, m;
	read(n), read(m);
	for (int i = 1, x, y; i <= m; i++) {
		read(x), read(y);
		add(x, y);
		add(y, x);
	}
	for (int i = 1; i <= n; i++)
		if (!vis[i]) {
			root = i;
			Tarjan(i, 0);
		}
	sort(ans + 1, ans + answer + 1);
	write(answer);
	putchar('\n');
	for (int i = 1; i <= answer; i++)  {
	    write(ans[i]);
	    putchar('\n');
	}
	return 0;
}

请各位大佬看看哪里有问题

2021/6/24 14:35
加载中...