基本思想:
只关注了入度和联通问题, 没有关注到两个用例点:
1. 这个题目空树也算树;
2. 一个节点的时候, 自环不构成树;
所以一个树的定义:
树内除了根节点一个结点入度为 0, 其他所有入度都为 1;
关键点:
抓住定义;
- #include<iostream>
- #include<string>
- #include<vector>
- #include<map>
- #include<set>
- using namespace std;
- const int maxn = 10100;
- int father[maxn];
- int inputcnt[maxn];
- void init() {
- for (int i = 0; i <= maxn; i++)
- father[i] = i;
- fill(inputcnt, inputcnt + maxn, 0);
- }
- int findfather(int x) {
- while (x != father[x]) {
- x = father[x];
- }
- return x;
- }
- void unfather(int a, int b) {
- int aa = findfather(a);
- int bb = findfather(b);
- father[aa] = bb;
- }
- int cntnum(set<int>s) {
- int cnt = 0;
- for (auto it = s.begin(); it != s.end(); it++) {
- if (father[*it] == *it)
- cnt++;
- }
- return cnt;
- }
- int main() {
- int cnt = 0;
- while (1) {
- cnt++;
- set<int>se;
- init();
- int a, b;
- while (cin>> a>> b) {
- if (a == 0)
- break;
- if (a == -1)
- return 0;
- inputcnt[b]++;
- se.insert(a);
- se.insert(b);
- unfather(a, b);
- }
- bool flag = true;// 是否由入度为 2 的点;
- bool zerocnt=0;
- for (auto it = se.begin(); it != se.end(); it++) {
- if (inputcnt[*it]> 1)
- flag = false;
- else if (inputcnt[*it] == 0)
- zerocnt++;
- }
- if (zerocnt != 1)
- flag = false;
- if (!flag || cntnum(se)> 1) {
- // 如果存在入度为 2
- cout << "Case" << cnt << "is not a tree." << endl;
- }
- else {
- cout << "Case" << cnt << "is a tree." << endl;
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3449166.html