Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:第一个并查集,留念

Posted by dqsy201204160127 at 2014-11-10 21:04:38 on Problem 1611
In Reply To:第一个并查集,留念 Posted by:fzhang at 2011-12-20 13:32:31
#include <iostream>
using namespace std;

#define MAXN 30000
int father[MAXN],rank[MAXN];

void Init(int n)
{
    int i;
    for(i=0; i<n; i++)
    {
        father[i]=i;
        rank[i]=1;
    }
}

int Find_Set(int x)
{
    if(x!=father[x])
    {
        father[x]=Find_Set(father[x]);
    }
    return father[x];
}

void Union(int x,int y)
{
    x=Find_Set(x);
    y=Find_Set(y);
  //  if(x==y)return;

if(x!=y)
{
    if(rank[x]>=rank[y])
    {
        father[y]=x;
        rank[x]=rank[x]+rank[y];
    }
    else
    {
        father[x]=y;
        rank[y]=rank[y]+rank[x];
    }
}
}

int main()
{
    int n,m,k,first,next;
    int i,j;
    while(cin>>n>>m)
    {

        if(n==0 && m==0)break;
        Init(n);

        for(i=0; i<m; i++)
        {
            cin>>k>>first;
            for(j=1; j<k; j++)
            {
                cin>>next;
                Union(first,next);
            }
        }
        cout<<rank[father[0]]<<endl;
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator