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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

提交好几遍了,每次都wa,题上,论坛里的数据都过了,就是wa,并查集做的,求大神。

Posted by 20020420 at 2018-09-29 11:38:58 on Problem 1308
#include<cstdio>
int m,n,f[101],rank[101],num=0,swc=0;
int getf(int);
void merge(int,int);
int main()
{
    while(scanf("%d%d",&n,&m)==2 && m!=-1 && n!=-1)
    {
        num++;
        int x,y,sum=0,book[50001];
        
        for(int i=1;i<=101;i++)//更新 
        {
            f[i]=i;
            book[i]=0;
        }
        swc=0;
        
        if(n==m && n==0)//n,m输入 
        {
            printf("Case %d is a tree.\n",num);
            continue;
        }
        if(getf(n)==getf(m))
        {
            swc=1;
        }
        else
        {
            book[n]=1;
            book[m]=1;
            merge(n,m);
        }
        
        while(scanf("%d%d",&x,&y)==2 && x && y)//后续 
        {
            if(getf(x)==getf(y))
            {
                swc=1;
            }
            else
            {
                book[x]=1;
                book[y]=1;
                merge(x,y);
            }
        }
        
        for(int i=1;i<=101;i++)//几个树 
        {
            if(book[i]==1 && i==getf(i))
            {
                sum++;
            }
        }
        
        if(sum!=1)
        {
            swc=1;
        }
        
        if(swc==1)//输出 
        {
            printf("Case %d is not a tree.\n",num);
        }
        else
        {
            printf("Case %d is a tree.\n",num);
        }
    }
    
    getchar();
    getchar();
    
    return 0;
}

int getf(int x)
{
    int r,j,k;
    r=x;
    while(r!=f[r])
    {
        r=f[r];
    }
    k=x;
    while(k!=r)
    {
        j=f[k];
        f[k]=r;
        k=j;
    }
    return r;
}

void merge(int x,int y)
{
    int i,j;
    i=getf(x);
    j=getf(y);
    if(i!=j)
    {
        if(j!=y)
        {
            swc=1;
            return ;
        }
        f[j]=i;
        if(rank[i]<rank[j])
        {
            rank[i]=rank[j]+1;
        }
        if(rank[i]==rank[j])
        {
            rank[i]++;
        }
    }
    return ;
}

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