東京大学 情報理工学系研究科 電子情報学専攻 2020年8月実施 専門 第3問

标签：

• Tokyo-University
• Union-Find-Data-Structure

Author

adj-matrix, 祭音Myyura

Description

$N$ 個の物体があるフィールド上を移動している。時刻 $t$ において2つの物体 $a,b$ が接触すると $(t,a,b)$ の三つ組みが記録されるものとする。2つの物体は一度接触すると同値関係となり、同じ同値類に所属する。各同値類は最初に単独の物体を含んでいるものとする。同値類に含まれる物体が他の同値類に含まれる物体と接触すると、それらの同値類は1つの同値類に併合する。以下の問いに答えよ。

(1) 次の疑似コードは、各物体の同値類を記録する union-find アルゴリズムを示している。init 関数は、同値類を記録する配列 parent の初期化を行う（配列 sizes はこの問いでは無視せよ）。上記の三つ組みが記録される度に union 関数が実行されて parent を更新する。$N=6$ であるとき、以下の三つ組みが記録された後の配列 parent の内容を示せ。

$$(1,0,3),(2,4,2),(3,1,5),(4,0,1)$$

(2) find 関数および union 関数について最悪時間計算量のオーダを理由と共に記せ。

(3) 配列 sizes を用いて、各同値類に含まれる物体の数を記録することを考える。疑似コード中の (X) と (Y) を埋めて、関数 size が指定された物体 $a$ を含む同値類中の物体の数を返すようにせよ。(X)、(Y) には複数行を記してもよい。

(4) 配列 sizes を用いて union 関数を変更することで、union および find 関数の時間計算量を改善することが可能になる。疑似コード中の (X) を変更して示せ。また、改善された union 関数の最悪時間計算量のオーダを理由と共に示せ。

(5) 指定された物体 $a$ と $b$ が同値となった時刻を求めることを考える。アルゴリズムの変更の方法を述べ、この時刻を求める関数の手続きを説明せよ。また、その関数の最悪時間計算量のオーダを理由と共に示せ。

int parent[N];
int sizes[N];

void init() {
    for (int i = 0; i < N; ++i) {
        parent[i] = i;
        sizes[i] = 1;
    }
}

int find(int i) {
    while (parent[i] != i) {
        i = parent[i];
    }
    return i;
}

void union(int a, int b) {
    int i = find(a);
    int j = find(b);
    parent[i] = j;
    (X)
}

int size(int a) {
    (Y)
}

题目描述

场地上有 $N$ 个移动物体。物体 $a,b$ 在时刻 $t$ 接触时，记录三元组 $(t,a,b)$。任意两个物体一旦接触过，就进入同一等价关系、属于同一等价类。初始时每个等价类只含一个物体；某类中的物体与另一类中的物体接触时，两类合并。

(1) 下页伪代码给出跟踪各物体等价类的并查集算法。init 初始化记录等价类的数组 parent；本问忽略 sizes。每记录一个上述三元组就执行 union 更新 parent。当 $N=6$，依次记录

$$(1,0,3),\ (2,4,2),\ (3,1,5),\ (4,0,1)$$

后，写出数组 parent 的内容。

(2) 分别说明函数 find、union 的最坏时间复杂度阶，并给出理由。

(3) 用数组 sizes 记录每个等价类所含物体数。填写伪代码中的 (X)、(Y)，使 size(a) 返回含指定物体 $a$ 的等价类大小；(X)、(Y) 均可填写多行。

(4) 利用 sizes 修改 union 中的 (X)，以改善 find、union 的时间复杂度。写出修改后的代码，并说明改进后 union 的最坏时间复杂度阶及理由。

(5) 需要查询指定物体 $a,b$ 在什么时刻成为等价。说明应如何修改算法以及查询函数的过程，并给出该函数的最坏时间复杂度阶及理由。

题目给出的并查集代码为：

int parent[N];
int sizes[N];

void init() {
    for (int i = 0; i < N; ++i) {
        parent[i] = i;
        sizes[i] = 1;
    }
}

int find(int i) {
    while (parent[i] != i) {
        i = parent[i];
    }
    return i;
}

void union(int a, int b) {
    int i = find(a);
    int j = find(b);
    parent[i] = j;
    (X)
}

int size(int a) {
    (Y)
}

Kai

(1)

時刻	parent[0]	parent[1]	parent[2]	parent[3]	parent[4]	parent[5]
初期	0	1	2	3	4	5
1	3	1	2	3	4	5
2	3	1	2	3	2	5
3	3	5	2	3	2	5
4	3	5	2	5	2	5

(2)

どちらも最悪 $\boxed{O(N)}$。木が長さ $N-1$ の鎖になる場合、find は根まで $N-1$ 本の親ポインタをたどる。union は find を2回呼び、その後の処理は定数時間である。

(3)

(X)：

if (i != j) {
    sizes[j] += sizes[i];
}

(Y)：

return sizes[find(a)];

既に同じ同値類なら大きさを加算しない。

(4)

(X) を次のようにする。

if (i == j) return;
if (sizes[i] > sizes[j]) {
    parent[i] = i;
    parent[j] = i;
    sizes[i] += sizes[j];
} else {
    sizes[j] += sizes[i];
}

小さい木を大きい木の根に接続する。sizes[i] > sizes[j] の場合は、空欄の直前で行われた parent[i] = j を parent[i] = i で戻してから、$j$ を $i$ の子にする。

頂点の深さが1増すたびに、その頂点を含む木の大きさは少なくとも2倍になる。従って深さは高々 $\lfloor\log_2N\rfloor$ であり、find、union とも最悪 $\boxed{O(\log N)}$ となる。

(5)

三つ組みを時刻順に処理し、(4) の併合を用いる。根 $x$ を別の根の子にしたとき、その親辺の作成時刻を time[x] = t と記録する。同じ同値類内の接触では変更しない。履歴を保つため経路圧縮は行わない。

問い合わせでは $a,b$ からそれぞれ根までの経路を求める。根が異なるなら未接続である。同じ根なら、両経路を根側から比較して最深共通祖先 $c$ を求め、$a\leadsto c$ と $b\leadsto c$ 上の全親辺の時刻の最大値を返す。

2頂点はこの道上の全ての併合が完了した時点で初めて接続されるので、この最大値が求める時刻となる。$a=b$ なら初期時刻を返す。

木の高さは $O(\log N)$ であり、2本の経路の取得・比較・最大値の計算はいずれもその長さに比例する。従って最悪時間は $\boxed{O(\log N)}$ である。