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

Posted by 834208094 at 2013-06-08 17:37:35 on Problem 1611
#include <iostream>
#include<string>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
int f[30010], ju[30010];
int con[15000000];
int getparent(int k)
{
    if(k == f[k]) return k;
    else
    {
        f[k] = getparent(f[k]);
        return f[k];
    }
}
int main()
{
    //freopen("D:\\CPPProgram\\ACM\\in.txt", "r", stdin);
    int n, m;
    while(1)
    {
        scanf("%d %d", &n, &m);
        if(m == 0 && n == 0) break;
        int cnt = 0;
        memset(ju, 0, sizeof ju);
        for(int i=0; i<n; i++)
        {
            f[i] = i;
        }
        for(int i=0; i<m; i++)
        {
            int num;
            scanf("%d", &num);
            for(int j=0; j<num; j++)
            {
                scanf("%d",&con[cnt]);
                cnt++;
            }
            for(int j=cnt-num; j<cnt-1; j++)
            {
                int p1, p2;
                p1 = getparent(con[j]);
                p2 = getparent(con[j+1]);
                if(p1 != p2)
                {
                    f[p1] = p2;
                }
            }
        }
        int p = getparent(0);
        int ans = 0;
        for(int i=0; i<cnt; i++)
        {
            if(ju[con[i]] == 0)
            {
                ju[con[i]] = 1;
                if(getparent(con[i]) == p)
                    ans++;
            }
        }
        if(ju[0] == 0) ans++;
        printf("%d\n", ans);
    }
    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