POJ_1308_Is It A Tree?

基德KID.1412

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, mark = false;branch = node = 0, flag = true;while (a > 0){        //自己不可指向自己，并且已经有父亲，就不可再接一个父亲了if (flag && (a == b || pre != b))flag = false;    //一旦出现上述情况，就可能是树了if (flag)    //判断是否有回路{A = find (a);    //寻找终极父节点B = find (b);if (A == B)//并查集的知识，本来已经属于同一集合，现在又合并，说明有回路flag = false;}if (flag){pre = a;    //有向图合并节点if (!mark[a])node++;    //累计节点数if (!mark)node++;mark[a] = mark = 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;}