人人狠狠综合久久亚洲,久久精品国产色蜜蜜麻豆,成人国内精品久久久久影院

2011年4月

日

一

二

三

四

五

六

統計

隨筆 - 29
文章 - 0
評論 - 2
引用 - 0

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

閱讀排行榜

評論排行榜

并查集 POJ2524

已知有n個大學生，其中有m對宗教信仰相同的學生，請你估算這n個學生中最多有多少種宗教信仰。
依舊是簡單的并查集應用。宗教信仰的最大值為學生數n，因此一開始把n個學生作為n個集合，對給出的每對大學生 a 和 b ，如果他們在不同的集合，就合并他們，然后宗教數減一。這次依舊用到了路徑壓縮，只不過上一次寫的是非遞歸，這次寫了一個遞歸版本。也就是搜索完成回溯的時候"順便"將當前節點的父節點直接指向祖先節點。

題目大意解釋來自Slyar Home (www.slyar.com) 轉載請注明，謝謝合作。

/*如果兩個學生的信仰一樣

則總的宗教個數減一 */

#include<iostream>

#include<stdio.h>

using namespace std;

int sum,n,m;

int father[50001];

void makeset(int x)

{

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

{

father[i]=i;

}

int findset(int x)//查

{

if(x!=father[x])

{

father[x]=findset(father[x]);

}//回溯

return father[x];

}

void Union(int a,int b)

{

int x=findset(a);

int y=findset(b);

if(x==y)

return;

sum=sum-1;

father[y]=x;

}

int main()

{

int l=1;

while(scanf("%d%d",&n,&m)!=EOF)

{ if(n==0&&m==0)

break;

sum=n;

makeset(n);

int first,second;

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

{

scanf("%d%d",&first,&second);

Union(first,second);

}

printf("Case %d: %d\n",l,sum);

l++;

}

return 0;

}

posted on 2011-03-30 11:24 Yiner 閱讀(319) 評論(0) 編輯收藏引用所屬分類: 并查集

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 并查集 HDU1863 并查集~最小生成樹 HDU1233 并查集 HDU1232 并查集 HDU1856 并查集 HDU1213 并查集 POJ2524 并查集 POJ1611 并查集

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

Yiner的ACM

統計