Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 简单并查集就好了，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: