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

简单并查集就好了,1A

Posted by godman at 2017-03-16 20:53:15 on Problem 1308 and last updated at 2017-03-16 20:53:24
#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;


int num=1;
set<int>s;
int pre[100000+100];
int flag;
void init()
{
    for(int i=1;i<=100000;i++) pre[i]=i;
    flag=0;
    s.clear();
}

int find(int x)
{
    return x==pre[x]?x:pre[x]=find(pre[x]);
}

int main()
{
    int x,y;
    init();
    while(~scanf("%d%d",&x,&y)&&(x!=-1&&y!=-1))
    {
        if(x==0&&y==0)
        {
            if(flag==0){
            int cnt=0;
            for(set<int>::iterator it=s.begin();it!=s.end();it++)
            {
                if(pre[*it]==*it) cnt++;
            }
            if(cnt>1) flag=1;
            }
           if(flag) printf("Case %d is not a tree.\n",num++);
           else printf("Case %d is a tree.\n",num++);
           init();
           continue;
        }
        else if(!flag)
        {
            s.insert(x);
            s.insert(y);
            int px=find(x);
            int py=find(y);
            if(px==py) flag=1;
            else if(y!=find(y)){
                flag=1;
            }
            else pre[py]=px;
        }
    }
}

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