1308:Is It A Tree?

keyword

有向グラフ　木　C++

概要

有向グラフが与えられたとき、それが木であるかどうかを判定する問題。
これもサイズに関する記述が無かったのでとりあえず愚直に実装してみる。根の検出が頭悪かったり変数名は明らかにfromじゃなくてtoだよねとか色々問題はあるけど0msでAC。きっとサイズが小さかったんだろう。

int main(){
    map<int, vector<int> > list;
    set<int> root, node, from;
    set<int> visited;
    int x, y, cnt=1, r, isTree, nEdge;
    queue<int> Q;
    while(scanf("%d%d",&x,&y)){
        if(x==-1 && y==-1) break;
        isTree = true;
        nEdge = 0;
        root.clear();
        node.clear();
        visited.clear();
        from.clear();
        list.clear();
        while(!Q.empty()) Q.pop();
        while(!(x==0 && y==0)){
            list[x].PB(y);
            node.insert(x);
            node.insert(y);
            from.insert(y);
            scanf("%d%d",&x,&y);
            nEdge++;
        }
        if(node.empty()) goto end;
        if(nEdge != SZ(node)-1){
            isTree = false;
            goto end;
        }
        EACH(node,it)if(from.find(*it)==from.end())root.insert(*it);
        if(SZ(root)!=1){
            isTree = false;
            goto end;
        }
        r = *root.begin();
        Q.push(r);
        visited.insert(r);
        while(!Q.empty()){
            int t = Q.front(); Q.pop();
            EACH(list[t],it){
                if(visited.find(*it)==visited.end()){
                    visited.insert(*it);
                    Q.push(*it);
                }
            }
        }
        if(SZ(visited)!=SZ(node)){
            isTree = false;
        }

        end:;
        if(isTree) printf("Case %d is a tree.\n", cnt++);
        else printf("Case %d is not a tree.\n", cnt++);
    }

    return 0;
}