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

题意看了好久~~擦汗 其实是道并查集水题 其实就是求多少人被0感染了

Posted by wtml at 2017-09-18 11:34:11 on Problem 1611
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 30000+100;
int par[maxn];
int rank[maxn];

//初始化
void init(int n)
{
    for(int i=0;i<n;i++)
    {
        par[i]=i;
        rank[i]=0;
    }
}

int find(int x)
{
    if(par[x]==x)
    {
        return x;
    }
    else
    {
        return par[x] = find(par[x]);
    }
}

void unite(int x,int y)
{
    x = find(x);
    y = find(y);
    if(x==y) return;

    if(rank[x]<rank[y])
    {
        par[x]=y;
    }
    else
    {
        par[y]=x;
        if(rank[x]==rank[y]) rank[x]++;
    }
}

int num[maxn];

int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;
        init(n);
        int z;
        for(int i=0;i<m;i++)
        {
           cin>>z;
           scanf("%d",&num[0]);
           for(int i=1;i<z;i++)
           {
              scanf("%d",&num[i]);
              unite(num[0],num[i]);
           }
        }
           int ans=0;
        for(int i=0;i<n;i++)
        {
            if(find(i)==par[0])
            {
               ans++;
            }
        }
        cout<<ans<<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