给定一个有向图, 判断其是否是一棵树
要求 (1) 除了根节点外, 每个节点只有唯一的前驱
(2) 从根节点出发, 到任何节点有且只有一条路径
思路
1. 要求(1) 可以通过记录每个节点的前驱决定, (2) 可以从根节点 dfs, 搜不到的点不是树, 搜到的点在(1)符合条件的情况下, 只有一条路径
2. 具体实现的话可以用 map[node*, node*]
3. 最终使用的并查集, 使用并查集的过程要注意几个判断条件
3.1 (1, 2) (2, 1) 不是树, 判断条件是 if(ed == find(st)) 假如经过寻找, 一个节点的父亲还是他自己, 说明出现了环
3.2 一个节点不能被有两个father, 所以当需要添加 father 的节点已经有了 father 时, 有错
3.3 只有一个根节点, 所以 father[x] == x 的节点有且仅有一个
代码
#include <iostream>
#include <stdio.h>
#include <set>
using namespace std; int father[]; int find(int x) {
if(x != father[x]) {
father[x] = find(father[x]);
}
return father[x];
} int main() {
freopen("testcase.txt", "r", stdin);
int st, ed;
int cases = ;
while(scanf("%d%d", &st, &ed) != EOF && st >= && ed >= ) {
cases ++;
set<int> record;
for(int i = ; i < ; i ++) {
father[i] = i;
}
bool flag = true;
while(st != && ed != ) {
if(ed != father[ed]) {
flag = false;
break;
}else{
int res = find(st);
if(res == ed) {
flag = false;
break;
}
father[ed] = res;
}
record.insert(st);
record.insert(ed);
scanf("%d%d", &st, &ed);
} while(st != || ed != )
scanf("%d%d", &st, &ed); int times = ;
for(set<int>::iterator it_set = record.begin(); times < &&it_set != record.end(); it_set++) {
int num = *it_set;
if(father[num] == num)
times++;
}
if(times > )
flag = false;
if(flag)
printf("Case %d is a tree.\n", cases);
else
printf("Case %d is not a tree.\n", cases); }
return ;
}