求调,WA#3,4,5,6
查看原帖
求调,WA#3,4,5,6
167697
BartAllen楼主2024/7/16 13:02
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;
const int M = 1e6 + 5;

int n, tot, u, v, ans = 2147483647, num, a, b;
int head[N * 2], ver[M * 2], edge[M * 2], nxt[M * 2];
int low[N * 2], dfn[N * 2];
bool cut[N * 2];

void add(int x, int y) {
	ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}

void tarjan(int x, int fa) {
	dfn[x] = low[x] = ++num;
	for (int i = head[x]; i; i = nxt[i]) {
		int y = ver[i];
		if (y == fa) continue; 
		if (!dfn[y]) {
			tarjan(y, x);
			low[x] = min(low[x], low[y]);
			if (low[y] >= dfn[x] && x != a && y != b && 
				((dfn[y] <= dfn[a] && dfn[y] > dfn[b]) || (dfn[y] > dfn[a] && dfn[y] <= dfn[b])))
					ans = min(ans, x);
		}
		else if (y != fa) low[x] = min(low[x], dfn[y]);
	}
	return;
}

int main() {
	scanf("%d", &n);
	while (1) {
		scanf("%d%d", &u, &v);
		if (u == 0 && v == 0) break;
		if (u == v) continue;
		add(u, v); add(v, u);
	}
	scanf("%d%d", &a, &b);
	tarjan(1, 0);
	if (ans == 2147483647) printf("No solution\n");
	else printf("%d\n", ans);
	return 0; 
}
2024/7/16 13:02
加载中...