1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
digraph G {
0;
1;
2;
3;
4;
5;
6;
7;
8;
9;
10;
11;
12;
13;
0 -> 1 [taillabel="0-1", ];
0 -> 2 [taillabel="0-2", ];
1 -> 6 [taillabel="1-6", ];
2 -> 3 [taillabel="2-3", ];
2 -> 4 [taillabel="2-4", ];
2 -> 5 [taillabel="2-5", ];
3 -> 7 [taillabel="3-7", ];
4 -> 5 [taillabel="4-5", ];
5 -> 9 [taillabel="5-9", ];
6 -> 8 [taillabel="6-8", ];
7 -> 8 [taillabel="7-8", ];
9 -> 10 [taillabel="9-10", ];
10 -> 12 [taillabel="10-12", ];
12 -> 11 [taillabel="12-11", ];
}
digraph G {
0;
1;
3;
5;
6;
7;
9;
10;
11;
0 -> 1 [taillabel="0-1", ];
0 -> 3 [taillabel="2-3", ];
0 -> 5 [taillabel="2-5", ];
0 -> 5 [taillabel="4-5", ];
1 -> 6 [taillabel="1-6", ];
3 -> 7 [taillabel="3-7", ];
5 -> 9 [taillabel="5-9", ];
7 -> 6 [taillabel="7-8", ];
9 -> 10 [taillabel="9-10", ];
10 -> 11 [taillabel="12-11", ];
}
# union-find sets
0 -> {0, 2, 4}
1 -> {1}
2 -> {0, 2, 4}
3 -> {3}
4 -> {0, 2, 4}
5 -> {5}
6 -> {6, 8}
7 -> {7}
8 -> {6, 8}
9 -> {9}
10 -> {10, 12}
11 -> {11}
12 -> {10, 12}
13 -> {13}
# g -> g'
0 -> 0
1 -> 1
2 -> 0
3 -> 3
4 -> 0
5 -> 5
6 -> 6
7 -> 7
8 -> 6
9 -> 9
10 -> 10
11 -> 11
12 -> 10
13 -> 13
|
