题解 | #Is It A Tree?#

【基于并查集判断树】

+无环(a->b,b->a)：getRoot(a)!=b

+无多入(a->b,c->b)：parent[b]==b

+必连通：计算连通子图数

#include<iostream>
#include<map>
#include<string>
using namespace std;
int getRoot(map<int,int> parent,int i){
    while(parent[i]!=i){
        i = parent[i];
    }
    return i;
}
int main(){
    
    int a,b;
    for(int i=1;;i++){
        map<int,int> parent;
        bool isTree = true;
        while(1){
            cin>>a>>b;
            if(a==0&&b==0) break;
            if(a==-1&&b==-1) return 0;
            if(parent.find(a)==parent.end()) parent[a] = a;
            if(parent.find(b)==parent.end()) parent[b] = b;
            
            if(parent[b]==b && getRoot(parent,a)!=b){
                parent[b] = a;
            } else {
                isTree = false;
            }
        }
        int counter = 0;
        map<int,int>::iterator it = parent.begin();
        while(it!=parent.end()){
            if(it->first==it->second) counter++;
            it++;
        }
        if(counter>1) isTree = false;
        string ans = isTree?"":"not ";
        cout<<"Case "<<i<<" is "<<ans<<"a tree."<<endl;
    }
    return 0;
}