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 nzomkxia_beta at 2011-11-10 23:39:02 on Problem 1611
#include <stdio.h>
#include <stdlib.h>
#define N 30001

int set[N] = {0};
void init_set(int a)
{
    set[a] = -1;
}

int Find(int a)
{
    int root,temp,modify;
    root = a;
    while(set[root] >= 0)
    {
        root = set[root];
    }
    modify = a;
    while(modify != root)
    {
        temp = set[modify];
        set[modify] = root;
        modify = temp;
    }
    return root;
}

void Uni_set(int a, int b)
{
    int father_a = Find(a);
    int father_b = Find(b);
    if(set[father_a] >= set[father_b])
    {
        set[father_b] += set[father_a];
        set[father_a] = father_b;
    }
    else
    {
        set[father_a] += set[father_b];
        set[father_b] = father_a;
    }
}
int main(int argc, char *argv[])
{
    int n,m;
    int k;
    int i;
    int x,y;
    while(scanf("%d %d",&n,&m) && n > 0)
    {
        for(i = 0;i < n;i++)
        {
            init_set(i);
        }
        while(m--)
        {
            scanf("%d",&k);
            scanf("%d",&x);
            k--;
            while(k--)
            {
                scanf("%d",&y);
                Uni_set(x,y);
            }
        }
        printf("%d\n",0-set[Find(0)]);
    }
    return 0;
}#include <stdio.h>
#include <stdlib.h>
#define N 30001

int set[N] = {0};
void init_set(int a)
{
    set[a] = -1;
}

int Find(int a)
{
    int root,temp,modify;
    root = a;
    while(set[root] >= 0)
    {
        root = set[root];
    }
    modify = a;
    while(modify != root)
    {
        temp = set[modify];
        set[modify] = root;
        modify = temp;
    }
    return root;
}

void Uni_set(int a, int b)
{
    int father_a = Find(a);
    int father_b = Find(b);
    if(set[father_a] >= set[father_b])
    {
        set[father_b] += set[father_a];
        set[father_a] = father_b;
    }
    else
    {
        set[father_a] += set[father_b];
        set[father_b] = father_a;
    }
}
int main(int argc, char *argv[])
{
    int n,m;
    int k;
    int i;
    int x,y;
    while(scanf("%d %d",&n,&m) && n > 0)
    {
        for(i = 0;i < n;i++)
        {
            init_set(i);
        }
        while(m--)
        {
            scanf("%d",&k);
            scanf("%d",&x);
            k--;
            while(k--)
            {
                scanf("%d",&y);
                Uni_set(x,y);
            }
        }
        printf("%d\n",0-set[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