POJ 1308 Is It A Tree?
問題
グラフ上のノード番号が2つずつ入力される。前者から後者のノードへは有向辺が伸びているものとする。このグラフがひとつの木になっているか判定せよ。なお入力は複数のテストケースからなり、0 0がそのケースの入力の終わりを表し、2つとも負の数が与えられた場合はすべてのテストケースの入力の終わりを表す。
やりかた
有向グラフが木構造になるのはルートの入次数が0になり、それ以外のノードの入次数が1の時。なので入次数が0のノードが1つでない場合や入次数が2以上あるノードがあれば木にはならない。
ただこの方法だと連結でないグラフであるケースを検出できないので、UnionFindで入力をくっつけていってひとつの木になるか判定した。
なお、ノードがひとつもない場合は木であると判定するようだ。
以下ソース。
//UnionFindのコードは略 int deg[20001]; int main(int argc, char **argv){ int idx = 1; while(1){ int a, b; set<int> node; UnionFind uf; fill(deg, deg + 20000, 0); while(scanf("%d %d", &a, &b), a + b){ if(a <= -1 && b <= -1) goto L1; deg[b]++;//入次数をカウント node.insert(a); node.insert(b); uf.unite(a, b); } int root = 0; bool tree = true; for(set<int>::iterator it = node.begin(); it != node.end(); it++){ int c = *it; if(deg[c] >= 2) tree = false;//入次数が2より大きいのはダメ if(!uf.same(*(node.begin()), c)) tree = false;//連結でないグラフだったらダメ if(deg[c] == 0) root++; } if(root != 1 && !node.empty()) tree = false;//ルートがひとつ以上あるものはダメ printf("Case %d is %s\n", idx++, tree ? "a tree." : "not a tree."); } L1:; return 0; }
ノードが1から順になっていないのがうざい。
Get up! 明日のSUPER ST@R!