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

第一道并查集 泪流

Posted by qqgyp at 2011-06-07 14:29:16 on Problem 1611
#include <iostream>
using namespace std;
int father[30002];
int sum[30002];

int getfather(int v)
{
    if(father[v]==v)
    return v;
    return father[v] = getfather(father[v]);
}

void connect(int x,int y)
{
     int fx,fy;
     fx = getfather(x);
     fy = getfather(y);
     if(fx==fy)return;
     sum[fy] = sum[fx]+sum[fy];
     father[fx] = fy;
}

int main()
{
    int n,m;
    int i,num,fath;
    while(cin>>n>>m)
    {
        if(!n && !m)break;
        for(i=0;i<=n;i++)
        {
            father[i] = i;
            sum[i] = 1;
        }
        while(m--)
        {
            cin>>num;
            cin>>fath;
            num--;
            while(num--)
            {
                 cin>>i;
                 if(father[i]!=father[fath])
                 connect(i,fath);            
             }
        }
       cout<<sum[getfather(0)]<<endl;
    }
}

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