アルゴリズムオタク

アルゴリズムオタク at TECH

413:デフォルトの名無しさん
06/11/15 17:18:05
>>334
超亀レスだが、ポインタ書き換えによる単一化を使うと効率がいい。
C#っぽい擬似コードで。public省略。Nは物体数。

class Pair { int a; int b; }
class Cell { int n; Cell(int n) { this.n = n; } }

Cell[] MakeUnifiedCells(Pair[] pairs) {
　　Cell[] cells = new Cell[N]; // 要素はnull初期化
　　foreach (Pair pair in pairs) {
　　　　Cell cellA = cells[pair.a]; Cell cellB = cells[pair.b];
　　　　if (cellA == null && cellB == null) {
　　　　　　cells[pair.a] = new Cell(pair.b);
　　　　} else if (cellA == null) { // assert(cellB != null)
　　　　　　cellB.n = pair.a;
　　　　} else { // assert(cellA != null)
　　　　　　cellA.n = pair.b;
　　　　}
　　}
　　return ret;
}

int GetEquivalenceClass(int n, Cell[] cells) {
　　while (cells[n] != null) n = cells[n].n;
　　return n;
}

まず、MakeUnifiedCells(Pair[] pairs)を使って、Cell[] cellsを用意する。
物体nがどの同値類に属するかは、GetEquivalenceClass(n, cells)で求められる。

次ページ

続きを表示

1を表示