読者です 読者をやめる 読者になる 読者になる

解いた問題のソースコードと解説など。


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から順になっていないのがうざい。

しょげないでよBaby 眠れば治る