題目：

樣例：
input:
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
output:
1
0
2
998

思路：
如果道路數量為0，則直接輸出n-1。如果不為0，則在輸入后，求出有幾個fa,然后-1(把幾個fa連起來所需的線條個數）

代碼：

#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <queue> #define maxn 11111 using namespace std; int n,m,mi,mj; int fa[maxn],cnt[maxn]; int getfa(int x) {return (x==fa[x])?x:(fa[x]=getfa(fa[x])); } void merge(int x,int y) {int xx=getfa(x),yy=getfa(y);if (xx==yy) return;fa[xx]=yy; } int main() {while(cin>>n>>m){int cntt=0;if(m==0) cout<<n-1<<endl;else{memset(cnt,0,sizeof(cnt));for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++){cin>>mi>>mj;merge(mi,mj);}for(int i=1;i<=n;i++) cnt[getfa(i)]++;for(int i=1;i<=n;i++){//out<<"i="<<i<<" "<<"cnt[i]"<<cnt[i]<<endl;if(cnt[i]!=0) cntt++;} cout<<cntt-1<<endl;}}return 0; }

總結

以上是生活随笔為你收集整理的P1536 村村通 并查集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。