Graph Connectivity
http://acm.uva.es/p/v4/459.html
節点の数と枝を与えられて、何個のグラフに分けられるか答えよというもの。
そんなの、すべての節点を最初別々のグラフとしておいて、枝をもらうたびに枝の両側のグラフを併合していけば簡単に解けます。解けるはずです。なのにAcceptされない。
併合処理の中で、同じ配列から読み出しつつ書き込んでいたせいで不変であるべき値を自分で書き換えちゃっていたせいでした。
for( i=0; i<nodes; i++ ) if( parent[i]==parent[n1] ) parent[i]=parent[n2];
こんな短い一ブロックに含まれたバグに気付かないんだからアルゴリズムは怖い。正しくはこう。
pn1 = parent[n1]; pn2 = parent[n2]; for( i=0; i<nodes; i++ ) if( parent[i]==pn1 ) parent[i]=pn2;