[原]poj-2324(裸併合検査集)

テーマリンク:
http://poj.org/problem?id=2524
n個人は、mは人の宗教に対して同じで、出力は全部でいくつの異なる宗教がありますか？
コードは以下の通りです

#include<iostream>
#include<cstdio>
using namespace std;

#define M 500100
int par[M];
int h[M];
int n, m;

void init(int a)
{
  for(int i = 1; i <= a; i++)
  {
    par[i] = i;
    h[i] = 0;
  }
}
int Find(int a)
{
  if(par[a] != a)
  {
    return par[a] = Find(par[a]);
  }
  else return a;
}
void Union(int a,int b)
{
  a = Find(a);
  b = Find(b);
  if(a == b) return;
  else
  {
    if(h[a] > h[b]) par[b] = a;
    else
    {
      if(h[a] == h[b]) h[b]++;
      par[a] = b;
    }
  }
}


int main()
{
 int cases = 1;
  while(scanf("%d%d",&n,&m) == 2)
  {
    if(n == 0) break;
    init(n);
    int Count = 0;
    for(int i = 0; i < m; i++)
    {
      int a,b;
      scanf("%d%d",&a,&b);
      Union(a,b);
    }
    for(int i = 1; i <= n; i++)      
    {
      if(par[i] == i) Count++;   //            
    }
    cout<<"Case "<<cases++<<": "<<Count<<endl;
  }
  return 0;
}

以前はwaが何度も繰り返しましたが、visit[]配列を定義してvisit[par[i]を記録していますか？Orz。。。。 
 
作者：u 011652573发表于2014-3-3 19:27:19
原文のリンク
コメント：45
コメントを見る