Is It A Tree?
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 30470 | Accepted: 10369 |
Description
A tree is a well-known data structure that is either empty (null, void, nothing) or is a set of one or more nodes connected by directed edges between nodes satisfying the following properties.
There is exactly one node, called the root, to which no directed edges point.
Every node except the root has exactly one edge pointing to it.
There is a unique sequence of directed edges from the root to each node.
For example, consider the illustrations below, in which nodes are represented by circles and edges are represented by lines with arrowheads. The first two of these are trees, but the last is not.
In this problem you will be given several descriptions of collections of nodes connected by directed edges. For each of these you are to determine if the collection satisfies the definition of a tree or not.
There is exactly one node, called the root, to which no directed edges point.
Every node except the root has exactly one edge pointing to it.
There is a unique sequence of directed edges from the root to each node.
For example, consider the illustrations below, in which nodes are represented by circles and edges are represented by lines with arrowheads. The first two of these are trees, but the last is not.
In this problem you will be given several descriptions of collections of nodes connected by directed edges. For each of these you are to determine if the collection satisfies the definition of a tree or not.
Input
The input will consist of a sequence of descriptions (test cases) followed by a pair of negative integers. Each test case will consist of a sequence of edge descriptions followed by a pair of zeroes Each edge description will consist of a pair of integers; the first integer identifies the node from which the edge begins, and the second integer identifies the node to which the edge is directed. Node numbers will always be greater than zero.
Output
For each test case display the line “Case k is a tree.” or the line “Case k is not a tree.”, where k corresponds to the test case number (they are sequentially numbered starting with 1).
Sample Input
6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0 3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1
Sample Output
Case 1 is a tree. Case 2 is a tree. Case 3 is not a tree.
题解：
首先，这道题的题意是让我们判断当前这个图是否是一棵树。那么我们就可以根据树的性质来判断了，我们发现树的每一个点可以有多个出度，但只能有一个入度，所以我们是不是可以枚举当前图的所有点的入度大小，然后根据前面我们发现的性质来判断，显然是可以的。
这里我们要判断很多东西：
- 0 0 空树也是一棵树
- 1 1 自己指向自己肯定不合法
- 1 2 2 1 指过去又只回来也不合法
- 1 2 3 4 0 0 森林不是一棵树，所以不合法
下面的代码就是判断入度的做法
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int rd[2333333];
bool num[2333333];
int main()
{
int a, b, tot = 0;
while(1)
{
tot ++;
int cnt = 0;
for (int i = 1; i <= 200000; i++)
rd[i] = 0;
while(scanf("%d%d", &a, &b) != EOF)
{
if (a == -1 && b == -1)
return 0;
if (a == 0 && b == 0)
break;
num[a] = 1, num[b] = 1;
rd[b] ++, cnt = max(cnt, max(a, b));
}
int sum = 0, warn = 0;//sum表示根节点数量（用来判断森林），warn表示入度大于1的点的数量
for (int i = 1; i <= cnt; i++)
{
if (!rd[i] && num[i])//如果这个点在树里并且入度为零，那么就为根节点
sum++;
if (rd[i] > 1 && num[i])
warn++;
}
if (sum == 1 && !warn || (cnt == 0 && sum == 0 && warn == 0))//有可能为空树，需要特判（|| 后的内容）
printf("Case %d is a tree.\n", tot);
else
printf("Case %d is not a tree.\n", tot);
}
return 0;
}
然后我们发现这样做有些麻烦（其实不麻烦）
所以我们想更优美的数据结构——并查集
如果是一棵树，那么肯定在一个集合中，如果原来在一个集合，又有连在一起，那么肯定是不合法的，所以就return
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int fa[233333];
int num[233333];
int find(int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main()
{
int a, b;
int cnt = 0;
while (1)
{
int tot = 0;
cnt++;
bool flag = 0;
for (int i = 1; i <= 200000; i++)
fa[i] = i;
while(scanf("%d%d", &a, &b) != EOF)
{
if (a == 0 && b == 0)
break;
if (a == -1 && b == -1)
return 0;
num[++tot] = a;
num[++tot] = b;//这里是存下整张图，然后用来判断是否为森林
if (a == b)
{
flag = 1;
printf("Case %d is not a tree.\n", cnt);
break;
}
if (find(a) != find(b))
fa[find(a)] = find(b);
else
{
flag = 1;
printf("Case %d is not a tree.\n", cnt);
break;
}
}
if (flag)
{
while (a != 0 && b != 0)//读入不合法后的数据直到本组数据结束
scanf("%d%d", &a, &b);
continue;
}
if (!flag)
{
for (int i = 1; i <= tot; i++)
{
for (int j = 1; j <= tot; j++)
{
if (num[i] != num[j])
if (find(num[i]) != find(num[j]))//判断森林
{
printf("Case %d is not a tree.\n", cnt);
flag = 1;
break;
}
if (flag)
break;
}
if (flag)
break;
}
if (!flag)
printf("Case %d is a tree.\n", cnt);
}
}
return 0;
}