算法1
C++ 代码
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 1e6 + 1;
int dfn[N], low[N], tim = 0;
int cut[N], idx = 0;
int to[N], nxt[N], h[N];
int n, m;
int s1, s2;
void add(int u, int v){
to[++ idx] = v, nxt[idx] = h[u], h[u] = idx;
}
void Tarjan(int u){
dfn[u] = low[u] = ++ tim;
for(int i = h[u]; i; i = nxt[i]){
int v = to[i];
if(!dfn[v]){
Tarjan(v);
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u] && u != s1 && dfn[s2] >= dfn[v])
cut[u] = 1;
}
else low[u] = min(low[u], dfn[v]);
}
}
int main(){
scanf("%d",&n);
int x, y;
scanf("%d%d",&x,&y);
while(x != 0 && y != 0){
add(x, y);
add(y, x);
scanf("%d%d",&x,&y);
}
scanf("%d%d",&s1, &s2);
Tarjan(s1);
for(int i = 1;i <= n;i ++){
if(cut[i]){
printf("%d", i);
return 0;
}
}
puts("No solution");
return 0;
}