洛谷 UVA615 题解
本题应该是一个并查集的进阶题目，值得一做。
一、数据范围的给定
本题的题面是没有数据范围的差评，但是发现：结点编号小于
二、思路
2.1 题目分析
首先要从树的特点下手。
-
树是一个无向无环图。但在这题，它是有向的，因为要表示父子关系。
-
树一定只有一个根。本句话看似废话，实际上也是这题的关键之一。
-
一棵树上的任意两点一定在同一个点集当中。这句话包含了重要二字：点集。告诉了我们这题应该使用的算法——并查集。只有并查集能判断两点是否在同一点集当中。
2.2 算法流程
2.1 部分已经推出了使用的算法，那么流程应该也是比较好想的。
-
初始化。本题是多测题，应该将并查集的每个数（
0 \dots N ）都初始化，因为题目中没有说点的编号是连续的。 -
第一轮判断：是否有环。这里需要用到 2.1 中的特点
3 ：每读入两点，就把它们加进并查集。但如果说它们已经在同一集合中，说明它们之前已经有了一条边。可以直接判断它不是一棵树。 -
第二轮判断：是否只有一棵树。这里需要用到 2.1 中的特点
2 ：当搜索到多个结点的父亲是自己的时候，说明图中不止一个连通块，不是一棵树。 -
最后下结论：如果第
1 ，2 步都成功通过，说明它是一棵树，反之亦然。
三、代码
代码中的细节：
本代码在洛谷上已 AC，若找到 Hack 数据请及时通知我。
//程序算法：图论
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
bool vis[N];
int p[N],rk[N];
inline void make_set(int x)
{
p[x]=x;
rk[x]=1;
}
int find(int x)
{
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
int union_set(int x,int y)
{
x=find(x),y=find(y);
if(x!=y)
{
if(rk[x]<rk[y])swap(x,y);
p[y]=x;
if(rk[x]==rk[y])rk[x]++;
}
return x;
}
void fast_read()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
int main()
{
//freopen("input.in","r",stdin);
//freopen("output.out","w",stdout);
//fast_read();
int u,v,kase=0;
while(cin>>u>>v&&u>=0&&v>=0)
{
//初始化！！！
kase++;
for(int i=0;i<N;i++)make_set(i);
memset(vis,false,sizeof(vis));
//第一轮判断：是否有环
bool pd=true;
while(u!=0||v!=0)
{
if(find(u)==find(v))pd=false;//若它们的根相同，说明这两个点重复加入了树，是有环的。
else
{
vis[u]=vis[v]=true;//均在树内
union_set(u,v);
}
cin>>u>>v;//别漏掉！！
}
if(pd==false)
{
cout<<"Case "<<kase<<" is not a tree.\n";
continue;
}
//第二轮判断：是否只有一个根结点
pd=true;
int tot=0;//记录根结点数量
for(int i=0;i<N;i++)//因为编号不连续，所以要全部枚举，vis[]数组派上用场。
if(vis[i]&&find(i)==i)
{
tot++;
if(tot>1)
{
pd=false;
break;
}
}
if(pd)cout<<"Case "<<kase<<" is a tree.\n";
else cout<<"Case "<<kase<<" is not a tree.\n";
}
return 0;
}