这道题是一道并查集的题目。和普通并查集相比,主要有几点需要注意:
1、注意空树的处理。
2、如果在合并的时候,这两个点已经在树中,说明路径重复,不是合法的树。
/* POJ 1308 * By Ceeji * http://poj.org/problem?id=1308 * */ #include <iostream> #include <cstring> using namespace std; const int MAX_N = 200; int father[MAX_N]; bool has_point[MAX_N]; int case_number = 0; void init_set () { memset (father, 0, sizeof(father)); // 0 means that the father is itself. memset (has_point, 0, sizeof(has_point)); } int get_father (const int i) { if (father[i] == 0 || father[i] == i) { father[i] = i; return i; } int tmp = get_father(father[i]); father[i] = tmp; return tmp; } /* union : point x to y */ void set_union (const int x, const int y) { int fx = get_father(x); int fy = get_father(y); father[fx] = fy; } int maxof (const int x, const int y) { return x > y ? x : y; } int do_work () { init_set (); int s, t, max = 0; bool finish = false; while (cin >> s >> t) { if (s > 0 && t > 0) // if s or t is not greater than 0, it is the end descripter. { max = maxof (maxof (max, s), t); has_point[s] = true; has_point[t] = true; if (get_father(s) != get_father(t)) set_union(s, t); else { cout << "Case " << case_number << " is not a tree." << endl; finish = true; } } else { if (s == -1 && t == -1) { return 1; } break; } } if (!finish) { int f = get_father(max); for (int i = 2; i <= max; ++i) if (has_point[i] && get_father(i) != f) { cout << "Case " << case_number << " is not a tree." << endl; finish = true; break; } } if (!finish) cout << "Case " << case_number << " is a tree." << endl; return 0; } int main() { while (true) { ++case_number; if (do_work()) return 0; } return 0; } |