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 821631813 at 2014-05-24 20:15:15 on Problem 1611
#include <iostream>
#include  <cstdlib>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define inf 30005
#define maxn 505
int n,i;
int father[inf];
int rank[inf];
int a[inf];
using namespace std;
void start()
{
    for(i=0;i<=n-1;i++)
    {
        father[i]=i;
        rank[i]=1;
    }
}
int find(int x)
{
    int r=x;
    while(father[r]!=r)
    {
        r=father[r];
    }
    return r;
}
void join(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    if(fx==fy) return ;
    if(rank[fx]>=rank[fy])
    {
        father[fy]=fx;
        rank[fx]+=rank[fy];
    }
    else
    {
        father[fx]=fy;
        rank[fy]+=rank[fx];
    }
}
int main()
{
    void join(int x,int y);
    int find(int x);
    void start();
    int m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0) break;
        start();
        while(m--)
        {
            int t;
            scanf("%d",&t);
           // memset(a,0,sizeof(a));
            for(i=0; i<t; i++ )
            {
                scanf("%d",&a[i]);
                if(i!=0) join(a[i-1],a[i]);
            }
        }
        printf("%d\n",rank[find(0)]);
    }
    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