kaito_tateyama's blog

木の作り方

ABC138D Kiを本番で嘘解法で通してしまった(after_contestで気づいた)ので、ACコードと自分のコードにランダムにケースを入れてHackケースを探そう!と思いました。このとき、木のテストケースの作り方が分からなかったのでTwitterで教えてもらいました。以下、それらをまとめておきます。意見をくださった方、ありがとうございます。

便利なツール

グラフの可視化にはGRAPH×GRAPH が便利です。

木を順に構成する

Python3で書きました。

import itertools, random  
N = 11  
R = 10  
l = list(range(1,N))  
h = list(itertools.permutations(l))  
seed = list(h[R])  
graph = []  
edge = []  
for i in seed:  
    if len(graph) != 0:  
        edge.append([i, graph[random.randrange(len(graph))]])  
    graph.append(i)  
print(edge)  
for i in edge:  
    print("{} {}".format(i[0], i[1]))  

output

[[2, 1], [3, 1], [4, 2], [5, 3], [6, 2], [8, 4], [10, 4], [7, 2], [9, 2]]  
2 1  
3 1  
4 2  
5 3  
6 2  
8 4  
10 4  
7 2  
9 2  

GRAPH×GRAPHでの結果

木ができています!
# 原理
$1$から$N$までの順列からランダムにひとつとってきてseedとします。以下のように木を構成します。graphはその時点での木の頂点、edgeは出力する辺の集合を表します。
1.まずseed[0]graphに加える
2.seed[i]と、graphからひとつだけ任意に選んだ頂点Kをつなぐ。具体的には、edge[seed[i], K]を追加する。
3.seed[i]graphに加える。
以降、seed[i]がとれなくなるまで手順2,3を繰り返す。
手順2で連結かつ閉路が存在しないことが確認できるので、これは木になります。

注意点としては、このコードではitertools.permutationsに時間がかかっているので、適当に順列を指定してあげればよいです。

UnionFindを使う

これたぶん次の完全グラフを間引く方法と似ている気がします。(よく分からなかった)
おそらくKruscalがUnionFindをつかうので、それと近い…?

完全グラフを間引いて全域木を作る

(後でやる)

Prufer Sequence

https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence
(後でやる)