P8604 题解

ikunTLE · 2025-10-12 18:27:12 · 题解

思路

本题可以使用并查集。

这道题很难直接做，但是注意到 N 和 M 的范围都很小，可以枚举每个点进行判断加和。

当判断 i 点是不是关键点时，即判断删除 i 点后 u 和 v 是否连通。可以删除所有与 i 点相关的每一条边，删掉后用并查集判断是否连通即可。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e3+10,M=2e3+10;
struct edge{
    int u,v;
}ed[M];
int fa[N];
void _init(){
    for(int i=0;i<N;++i)
        fa[i]=i;
    return;
}
int _find(int x){
    if(x==fa[x])
        return x;
    fa[x]=_find(fa[x]);
    return fa[x];
}
void _merge(int x,int y){
    int xx=_find(x),yy=_find(y);
    if(xx!=yy)
        fa[xx]=yy;
    return;
}
int main(){
    _init();
    int n=read(),m=read();
    for(int i=1;i<=m;++i){
        ed[i]={read(),read()};
        _merge(ed[i].u,ed[i].v);
    }
    int u=read(),v=read();
    if(_find(u)!=_find(v))
        return printf("-1\n"),0;
    int res=0;
    for(int i=1;i<=n;++i)
        if(i!=u&&i!=v){
            _init();
            for(int j=1;j<=m;++j)
                if(ed[j].u!=i&&ed[j].v!=i)
                    _merge(ed[j].u,ed[j].v);
            if(_find(u)!=_find(v))
                ++res;
        }
    printf("%d\n",res);
    return 0;
}