http://poj.org/problem?id=1308
题意：判断这是不是一棵树。
思路：这个题还是有部分坑点的。首先空树也是一棵树，还有森林不是树。
关于森林的判断我是利用并查集把每一个点压缩路径，看一共有几个原始点，超过一个，则不是树是森林。
关于并查集
寻找以及压缩的代码
int Find(int x)
{
int _b,int _x=x;
while(belg[_x]!=_x) //压缩路径，找到它的最顶端的点。
{
_x=belg[_x];
}
while(belg[x]!=x) //把这一系列的点的父亲节点都更新到最顶端的点。
{
_b=belg[x];
belg[x]=_x;
x=_b;
}
return _x;
}
关于合并
int Union(int i,int j)
{
if(rand()&) //随机分配
{
belg[j]=i;
}
else
{
belg[i]=j;
}
}
#include <string.h>
#include <stdio.h>
#include <iostream>
#define l 10010 using namespace std; int belg[l]; int fin(int x)
{
int _b,_x=x;
while(belg[_x]!=_x&&belg[_x])
{
_x=belg[_x];
}
while(belg[x]!=x&&belg[x])
{
_b=belg[x];
belg[x]=_x;
x=_b;
}
return _x;
} int main()
{
// freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int m,n,ans,cas,father;
bool mark[l];
cas=;
while(scanf("%d%d",&m,&n),m!=-||n!=-)
{
ans=,father=;
memset(belg,,sizeof(belg));
memset(mark,false,sizeof(mark));
belg[n]=m;
mark[n]=true;
if(m==n&&m!=) ans=;
if(m==n&&m==) ans=;
else while(scanf("%d%d",&m,&n),m||n)
{
if(belg[m]==n) {ans=;continue;}
if(belg[n]) ans=;
if(n==m) ans=;
if(!belg[n]&&n!=m) belg[n]=m;
fin(n);
mark[n]=true;
}
for(int i=;i<;i++)
if(mark[i]) fin(i);
for(int i=;i<;i++)
{
if(father==&&mark[i]) {father=belg[i];continue;}
if(mark[i]&&belg[i]!=father) {
ans=;
break;
}
}
if(ans) printf("Case %d is a tree.\n",++cas);
else printf("Case %d is not a tree.\n",++cas);
}
return ;
}
测试数据：
1 2 2 3 3 1 5 6 0 0 0 0 0 0 1 2 3 4 4 5 5 3 0 0 2 1 3 1 4 1 5 1 0 0 2 1 3 1 4 1 0 0 1 2 4 5 5 4 0 0 1 2 1 3 1 4 1 5 0 0 -1 -1
答案
Case 1 is not a tree.
Case 2 is a tree.
Case 3 is a tree.
Case 4 is not a tree.
Case 5 is not a tree.
Case 6 is not a tree.
Case 7 is not a tree.
Case 8 is a tree.