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

第一个并查集,1A,16MS,附代码

Posted by speedcell4 at 2011-07-29 15:56:26 on Problem 1611
#include<iostream>
#define SIZE 30001
using namespace std;
int n,m,k,a[SIZE]={0},b[SIZE]={0};
void Init(void)
{
    for(int i=0;n-i>0;i++) a[i]=i;
}
int getFather(int n)
{
    if(a[n]!=n) return a[n]=getFather(a[n]);
    else return a[n];
}
void Union(int x,int y)
{
    int f_x=getFather(x);
    int f_y=getFather(y);
    a[f_x]=f_y;
}
int getCount(void)
{
    int count=1;
    for(int i=1;n-i>0;i++)
    {
        if(getFather(i)==getFather(0)) count++;
    }
    return count;
}
int main()
{
    while(scanf("%d %d",&n,&m),n||m)
    {
        Init();
        for(int i=0;m-i>0;i++)
        {
            scanf("%d",&k);
            for(int j=0;k-j>0;j++) scanf("%d",&b[j]);
            for(int j=1;k-j>0;j++) Union(b[j-1],b[j]);
        }
        printf("%d\n",getCount());
    }
}    

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