2. WA了好多次,最后发现是当空树的时候也是一棵树,fuck。。。
#include <iostream> #include <fstream> #include <string> #include <algorithm> #include <cstring> #include <stack> #include <queue> #define maxn 1000 using namespace std; int p[maxn], flag[maxn]; int getfather(int x) { return p[x] == x ? x : p[x] = getfather(p[x]); } int main() { int t = 1, a, b; while (cin >> a >> b && a != -1) { if (!a) { cout << "Case " << t++ << " is a tree." << endl; continue; } int is = 1, tail = 0; for (int i = 1; i < maxn; ++i) { p[i] = i; flag[i] = 0; } while (a) { if (is) { int ra = getfather(a), rb = getfather(b); if (ra == rb) { is = 0; } else { p[rb] = ra; flag[a] = flag[b] = 1; tail = max(tail, max(a, b)); } } cin >> a >> b; } if (!is) { cout << "Case " << t++ << " is not a tree." << endl; } else { int roots = 0; for (int i = 1; i <= tail; i++) { if (flag[i] && p[i] == i) { roots++; if (roots > 1) break; } } if (roots == 1) cout << "Case " << t++ << " is a tree." << endl; else cout << "Case " << t++ << " is not a tree." << endl; } } return 0; }