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

## Re:注意~!~!~!需要注意的数据

Posted by Dorrow at 2016-05-03 02:24:09 on Problem 1308
In Reply To:注意~!~!~!需要注意的数据 Posted by:xuhanqiu at 2006-08-18 09:48:42
```#include<iostream>
#include<cstring>
#include<cstdio>
#define mem(a,x) memset(a,x,sizeof(a))
#define inf (1<<29)
using namespace std;
typedef long long ll;
const int N = 100000;
int f[N + 5];
bool vis[N + 5];
void init (int n)
{
for (int i = 0; i <= n; ++i)
{
f[i] = i;
vis[i] = 0;
}
}
int getf (int x)
{
int xx = x;
while (x != f[x]) x = f[x];
return f[xx] = f[x];
}
bool Merge (int x, int y)
{
int fx = getf (x);
int fy = getf (y);
if (fx != fy)
{
f[fx] = fy;
return 0;
}
return 1;
}
int main()
{
int  kas = 0, x, y, mx = 0;
bool fd = 0;
init (N);
while (~scanf ("%d %d", &x, &y) )
{
if (x <0|| y <0) break;
if (x == 0 && y == 0)
{
if (fd)
{
printf ("Case %d is not a tree.\n", ++kas);
}
else
{
int only = 0;
for (int i = 1; i <= mx; ++i)
{
if (vis[i] && f[i] == i)
{
only++;
if (only > 1) break;
}
}
if (only > 1)
{
printf ("Case %d is not a tree.\n", ++kas);
}
else
{
printf ("Case %d is a tree.\n", ++kas);
}
init (N);
fd = 0, mx = 0;
}
}
else
{
mx = max (mx, max (x, y) );
vis[x] = vis[y] = 1;
if (fd) continue;
if (Merge (x, y) ) fd = 1;
}
}
return 0;
}

Followed by: