加边的无向图
加边的无向图
https://ac.nowcoder.com/acm/problem/14685
题目链接:https://ac.nowcoder.com/acm/problem/14685
思路:这道题是一个简单的并查集,只需要找出连通数的个数,然后对连通数的个数减去1就可以得到答案。
#include<iostream> using namespace std; int fa[100050]; int find(int x){ return x==fa[x] ? x:fa[x]=find(fa[x]); }//并查集找根 int main(){ int n,m; cin>>n>>m; for(int i=0;i<=n;i++){ fa[i]=i; } for(int i=1;i<=m;i++){ int a,b; cin>>a>>b; if(find(a)!=find(b)){ fa[find(a)]=find(b); } } int ans=0; for(int i=1;i<=n;i++){ if(fa[i]==i){ ans++; } } cout<<ans-1; return 0; }