正題

題目鏈接：
http://poj.org/problem?id=2524

---

大意

有n個學生，告訴你哪兩個學生的宗教相等，求校園里有多少個宗教。

---

解題思路

并查集鏈接就好了

---

代碼

#include<cstdio> using namespace std; int n,m,x,y,s,father[50001],t; int find(int x) {if (x!=father[x]) return father[x]=find(father[x]);else return father[x]; }//尋找祖先 int unionn(int x,int y) {int fa=find(x),fb=find(y);if (fa<fb) father[fb]=fa;else father[fa]=fb; }//連接 int main() {while (true){scanf("%d%d",&n,&m);if (n==0) break;t++;s=0;for (int i=1;i<=n;i++) father[i]=i;for (int j=1;j<=m;j++){scanf("%d%d",&x,&y);unionn(x,y);//連接}for (int i=1;i<=n;i++) if (father[i]==i) s++;//統計printf("Case %d: %d\n",t,s);} }

總結

以上是生活随笔為你收集整理的POJ2524——宗教(Ubiquitous Religions)【图论，并查集】的全部內容，希望文章能夠幫你解決所遇到的問題。

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