程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj-2524-Ubiquitous Religions

poj-2524-Ubiquitous Religions

編輯:C++入門知識

poj-2524-Ubiquitous Religions


題目大意:一個學校有n人,其中有m對人是具有相同的宗教信仰,
問這個學校裡信仰的宗教數最多有多少個。

解題思路:基礎的並查集。具有相同信仰的人歸為一個集合,

則最後的集合數量即為結果。求集合數量:判斷有多少個根節點,用到根節點的特征(其父節點為自己)

代碼如下:

#include
#include
#include
using namespace std;
int n,m;
int f[52014];
void init()
{
    for(int i=1; i<=n; i++)
        f[i]=i;
}
int find(int x)
{
    return f[x]==x?x:find(f[x]);
}
void unity(int a,int b)
{
    if(find(a)!=find(b))
        f[find(a)]=find(b);
}
int main()
{
    int ji=1;
    while(cin>>n>>m)
    {
        if(n+m==0)break;
        init();
        while(m--)
        {
            int a,b;
            cin>>a>>b;
            unity(a,b);
        }
        int ans=0;
        for(int i=1; i<=n; i++)
            if(f[i]==i)
                ans++;
        cout<<"Case "<

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved