POJ_1308_Is It A Tree?
http://poj.org/problem?id=1308
题意：就是判断给定输入是否是树
杭电的测试数据太弱，我以前的代码过不了下面第一个都能AC，北大貌似更弱，无语……
测试案例：
1 2 2 3 3 1 4 5 0 0 不是树，是森林
0 0 是一棵空树，是树
1 1 0 0 不可指向自己，不是树
1 3 3 2 5 2 0 0 不是树，2节点有2个父亲
可以利用树的性质：树枝数==节点数-1
#include <iostream>using namespace std;int pre[100005];bool mark[100005];int find (int a){while (a != pre[a])a = pre[a];return a;}int main(){bool flag;int a, b, i, k = 1, branch, node, A, B;while (scanf ("%d%d", &a, &b) != EOF){if (a < 0 && b < 0)break;if (!a && !b){printf ("Case %d is a tree.\n", k++);continue;}for (i = 1; i <= 100000; i++)pre[i] = i, mark[i] = false;branch = node = 0, flag = true;while (a > 0){ //自己不可指向自己，并且已经有父亲，就不可再接一个父亲了if (flag && (a == b || pre[b] != b))flag = false; //一旦出现上述情况，就可能是树了if (flag) //判断是否有回路{A = find (a); //寻找终极父节点B = find (b);if (A == B)//并查集的知识，本来已经属于同一集合，现在又合并，说明有回路flag = false;}if (flag){pre[b] = a; //有向图合并节点if (!mark[a])node++; //累计节点数if (!mark[b])node++;mark[a] = mark[b] = true; //标记节点branch++; //累计树枝数}scanf ("%d%d", &a, &b);}if (flag && branch == node - 1) //树枝数==节点数-1printf ("Case %d is a tree.\n", k++);else printf ("Case %d is not a tree.\n", k++);}return 0;}