题解 | #Is It A Tree?#

#include<iostream> #include<vector> #include<map> #include<set> using namespace std; int find(int x,vector<int> &father){ if(x != father[x]) father[x] = find(father[x],father); return father[x]; } void Union(int s,int e,vector<int> &father){ s = find(s,father); e = find(e,father); if(s != e) father[s] = e; } int main() { ios::sync_with_stdio(false); cin.tie(0); int s = 0,e = 0,cnt = 0,num = 0; bool flag = true; vector<int> father; map<int> indegree; set<pair><int> > Set; for(int i = 0;i <= 10000;++i) father.push_back(i); while(s != -1 && e != -1){ while(cin >> s >> e && s && e && s != -1 && e != -1){ if(Set.count(pair<int>(s,e)) == 0) Set.insert(pair<int>(s,e)); else flag = false; } if(s == -1 && e == -1) break; for(auto it : Set){ s = it.first,e = it.second; if(s != 0 || e != 0){ indegree[e]++; if(indegree[e] > 1) flag = false; if(indegree.find(s) == indegree.end()) indegree[s] = 0; Union(s,e,father); } else break; } num++; for(auto it : indegree) if(find(it.first,father) == it.first) cnt++; //排除可能存在的自环 int tag = 0; for(auto it : indegree) if(it.second == 0) tag++; if((cnt > 1 || flag == false || tag == 0 || tag > 1) && !Set.empty()) cout << "Case " << num << " is not a tree." << endl; else cout << "Case " << num << " is a tree." << endl; cnt = 0; father.clear(); for(int i = 0;i <= 10000;++i) father.push_back(i); indegree.clear(); flag = true; Set.clear(); } }</int></int></int></pair></int></int></int></int></set></map></vector></iostream>