求助0分【悬赏关注】
查看原帖
求助0分【悬赏关注】
637788
kimi0705楼主2023/1/17 13:43
#include <bits/stdc++.h>
using namespace std;
int n, a, b;
int dfn[200005], low[200005], cut[200005], head[200005];
int root, tim, cnt;
struct {
	int to;
	int next;
}edge[99999999];
void add(int x, int y) {
	cnt++;
	edge[cnt].next = head[x];
	edge[cnt].to = y;
	head[x] = cnt;
}
void tarjan(int x) {
	int flag = 0;
	low[x] = dfn[x] = ++tim;
	for (int i = head[x]; i; i = edge[i].next) {
		int y = edge[i].to;
		if (!dfn[y]) {		
			tarjan(y);
			if(low[y] >= dfn[x]) {
				flag++;
				if(flag > 1 || root != x) {
					if(dfn[y] <= dfn[b]) {
						cut[y] = true;
					}
				}
			}else{
				low[x] = min(low[x], low[y]);
			}
		}else{
			low[x] = min(low[x], dfn[y]);
		}
	}
}
int main() {
	cin >> n;
	while(1) {
		int x, y;
		cin >> x >> y;
		if(x || y) {
			add(x, y);
			add(y, x);
		}else break;
	}
	cin >> a >> b;
	root = a;
	tarjan(root);
	for (int i = 1; i <= n; i++) {
		if(cut[i]) {
			cout << i;
			return 0;
		}
	}
	cout << "No solution\n";
	return 0;
}
2023/1/17 13:43
加载中...