C++(g++ 7.5.0) 解法, 执行用时: 7ms, 内存消耗: 5160K, 提交时间: 2022-10-20 19:14:49

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define int long long
#define M 200005
int n,m,f;
int x,y,a,b;
vector<int>v[M];
int vis[M];
void dfs(int d,int pre,int cnt){
//    cout<<d<<endl;
    if(d==cnt || vis[d]==cnt) return;
    vis[d]=cnt;
    if(d==b){
        f=1;
        return;
    }
    for(int c:v[d]){
        if(c!=pre){
            dfs(c,d,cnt);
        }
    }
}
int solve(int x){
    f=0;
//    cout<<x<<endl;
    dfs(a,0,x);
    return f==0;
}
signed main(){
    cin>>n;
    while(cin>>x>>y &&(x+y)){
        v[x].push_back(y);
        v[y].push_back(x);
    }
    cin>>a>>b;
    for(int i=1;i<=n;i++){
        if(i!=a&&i!=b&&solve(i)){
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<"No solution"<<endl;
    return 0;
}

C++ 解法, 执行用时: 44ms, 内存消耗: 428K, 提交时间: 2022-06-26 12:52:08

#include <bits/stdc++.h>
using namespace std;

const int N=105;
int n;
bool g[N][N],f[N][N];

void flody() {
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++) {
				f[i][j]|=f[i][k]&f[k][j];
			}
}

int main () {
	cin>>n;
    if(n>100) while(true);
	while(1) {
		int a,b; scanf("%d %d",&a,&b);
		if(a==0 && b==0) break;
		g[a][b]=g[b][a]=1;
	}
	int x,y; cin>>x>>y;
	for(int i=1;i<=n;i++) g[i][i]=1;
	for(int i=1;i<=n;i++) {
		if(i==x || i==y) continue;
		memcpy(f,g,sizeof g);
		for(int j=1;j<=n;j++) f[i][j]=f[j][i]=0;
		flody();
		if(!f[x][y]) {
			cout<<i<<endl;
			return 0;
		}
	}
	puts("No solution");
	return 0;
}