柚子快報邀請碼778899分享：c++ 并查集（藍橋杯）

http://yzkb.51969.com/

P8604 [藍橋杯 2013 國 C] 危險系數(shù) - 洛谷 | 計算機科學教育新生態(tài) (luogu.com.cn)

#include

using namespace std;

const int N=1e5;

int n,m;

int f[N];

int a[N],b[N];

int u,v;

int res=0;

void init()

{

for(int i=1;i<=n;i++)

f[i]=i;

}

int find(int p)

{

if(f[p]!=p)

return f[p]=find(f[p]);

else

return p;

}

void Union(int x,int y)

{

int rx,ry;

rx=find(x);

ry=find(y);

if(rx!=ry)

f[rx]=ry;

}

bool chick(int p)

{

init();//初始化并查集

for(int i=1;i<=m;i++)

{

if(p==a[i]||p==b[i])

continue;

Union(a[i],b[i]);//刪除p節(jié)點后，再聯(lián)結(jié)

}

if(find(u)!=find(v))//u,v不在同一集合，說明p是關(guān)鍵點

return true;

else

return false;

}

int main()

{

ios::sync_with_stdio(false);

cin.tie(nullptr);cout.tie(nullptr);

cin>>n>>m;

init();//初始化并查集

for(int i=1;i<=m;i++)

{

cin>>a[i]>>b[i];

Union(a[i],b[i]);

}

cin>>u>>v;

if(find(u)!=find(v))//不在同一父節(jié)點下，說明不連通

{

cout<<-1;

return 0;

}

for(int i=1;i<=n;i++)//循環(huán)所有點，找關(guān)鍵點的個數(shù)

{

if(i!=u&&i!=v)//關(guān)鍵點不能是本身

{

if(chick(i))

res++;

}

}

cout<

return 0;

}

柚子快報邀請碼778899分享：c++ 并查集（藍橋杯）

http://yzkb.51969.com/

精彩文章