POJ 1611 The Suspects(特別無語的並查集)

POJ 1611 The Suspects(特別無語的並查集)

很簡單的一道題目，開始用的是並查集的分離集合森林做，不知道怎麼的特別不穩定，太奇怪了，WA無數次，無奈之下改成一維數組了。。sad

AC

#include 
#include 
#include 
#include 
#include 
#include 
#define PI acos(-1,0)
using namespace std;
const int maxn = 30010;
const int maxm = 100001;
#define lson left, m, id<<1
#define rson m+1, right, id<<1|1
#define min(a,b) (a>b)?b:a
#define max(a,b) (a>b)?a:b
using namespace std;

int father[50000];
int num[50000],n,m;

int Find(int r)
{
    int i = r,j;
    while(father[r]!=r)
    {
         r=father[r];
    }

    while(father[i]!=r)
    {
        j = father[i];
        father[i] = r;
        i = j;
    }
    return r;
}

void init()
{
	for(int i = 0;i < n;i++)
	{
		father[i] = i;
		num[i] = 1;
	}
}
void Merge(int l,int b)
{
    int y = Find(b);
        if(l != y)
        {
            father[y] = l;
        num[l] +=  num[y];
        }
}
int main()
{
	int j,k,l;
	while(~scanf("%d%d",&n,&m))
	{
		if(n==0 && m==0)
			break;
		init();
		int b;
		while(m--)
		{
			scanf("%d%d",&k,&l);

			int x = Find(l);
			for(j = 1;j < k;j++)
			{
				scanf("%d",&b);
				Merge(x,b);
			}

		}
	    printf("%d\n",num[Find(0)]);
	}
	return 0;
}

WA

#include 
#include 
#include 
#include 
#include 
#include 
#define PI acos(-1,0)
using namespace std;
const int maxn = 30010;
const int maxm = 100001;
#define lson left, m, id<<1
#define rson m+1, right, id<<1|1
#define min(a,b) (a>b)?b:a
#define max(a,b) (a>b)?a:b

using namespace std;

struct node
{
    int zhi , parent;
} T[maxn];

int Find(int x)
{
	return (x == T[x].parent) ? x : Find(T[x].parent);
}

void Merge(int x,int y)
{
    int fx,fy;

    fx = Find(x);
    fy = Find(y);
    if(fx!=fy)
    {
        T[fy].parent = fx;
        T[fx].zhi += T[fy].zhi;
    }
}

int main()
{
    int m,n,k;
    while (~scanf("%d%d",&n,&m))
    {
        if (n==0 && m==0) break;

        for(int j = 0; j

5 3

1 2

2 0 1

3 1 4 5


answer  3
有時是正確結果，有時不是，特別無語啊。







3