AtCoder NoviStepsを埋めてみる(12) 整数系探索問題 1Q以上の続きです。今回は Union-Find です。
素集合データ構造（disjoint-set data structure）とは、データの集合を素集合（互いにオーバーラップしない集合）に分割して保持するデータ構造のことです。
このデータ構造に対して
① Find: 特定の要素がどの集合に属しているかを求める。2つの要素が同じ集合に属しているかの判定にも使われる。
② Union: 2つの集合を1つに統合する。
これらの操作を Union-Find アルゴリズムと呼び、グラフの連結判定、サイクル検出などに使うことができます。
また ac-library-csharp というライブラリの Dsu クラスを使えば、自分でこのようなデータ構造を実装しなくても簡単に使用することができます。
Contents
C – Count Connected Components
C – Count Connected Components
問題の概要
N 頂点 M 辺の単純無向グラフが与えられる。グラフに含まれる連結成分の個数を求めよ。
基本問題です。Union-Find を使えば簡単に解けます。辺でつながっている頂点を Merge して最後に Groups メソッドを呼び出せば連結成分と各連結成分に属する頂点の配列が返されるので、dsu.Groups().Length を出力すればよいです。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); Dsu dsu = new Dsu(N); for (int i = 0; i < M; i++) { (int u, int v) = ReadInt2(); u--; v--; dsu.Merge(u, v); } int ans = dsu.Groups().Length; Console.WriteLine(ans); } } |
C – Connect Cities
問題の概要
N 個の都市と都市 A[i] と都市 B[i] を結ぶM 個の双方向道路がある。
どの都市からどの都市へもひとつまたは複数の道路をたどることで到達できるようにするためには、最低何個の道路を作ればよいだろうか？
連結成分が何個あるか求めれば、それらを連結させるために必要な道路の数がわかります。連結成分の個数 – 1 が解です。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); Dsu dsu = new Dsu(N); for (int i = 0; i < M; i++) { (int a, int b) = ReadInt2(); a--; b--; dsu.Merge(a, b); } int ans = dsu.Groups().Length; Console.WriteLine(ans - 1); } } |
C – Make it Forest
問題の概要
N 頂点 M 辺の単純無向グラフが与えられる。
グラフを森にするためには辺を最低何本削除する必要があるだろうか？
閉路を持たない（連結であるとは限らない）グラフを森（英: forest）といいます。森は各連結成分をみたとき、木になっています。木も閉路を持たず辺の数が頂点数よりも 1 少ないという性質があります。
なので（各連結成分に属する頂点 – 1）の総和が森であるために必要な辺の数です。M からこれを引いたものが解となります。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); Dsu dsu = new Dsu(N); for (int i = 0; i < M; i++) { (int u, int v) = ReadInt2(); u--; v--; dsu.Merge(u, v); } foreach (var group in dsu.Groups()) M -= group.Length - 1; Console.WriteLine(M); } } |
C – Virus
問題の概要
N 人の人が二次元平面上におり、人 i は座標 (X[i] ,Y[i]) にいる。
人 1 がウイルスに感染した。ウイルスに感染した人から距離が D 以内にいる人にウイルスは感染する。
十分に時間が経過したあと、各 i についてウイルスに感染しているか判定せよ。
Union-Find で距離が D 以内にある頂点を Merge していきます。頂点 i が 頂点 1 と同じ連結成分に属するのであれば “Yes”、そうでないなら “No” を出力します。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int D) = ReadInt2(); int[] X = new int[N]; int[] Y = new int[N]; for (int i = 0; i < N; i++) { (int x, int y) = ReadInt2(); X[i] = x; Y[i] = y; } Dsu dsu = new Dsu(N); for (int a = 0; a < N; a++) { for (int b = a + 1; b < N; b++) { if(Math.Pow(X[a] - X[b], 2) + Math.Pow(Y[a] - Y[b], 2) <= Math.Pow(D, 2)) dsu.Merge(a, b); } } for (int i = 0; i < N; i++) Console.WriteLine(dsu.Same(i, 0) ? "Yes" : "No"); } } |
C – Don’t be cycle
問題の概要
N 頂点 M 辺の単純無向グラフが与えられる。
このグラフから 0 本以上のいくつかの辺を削除してグラフが閉路を持たないようにするとき、削除する辺の本数の最小値を求めよ。
閉路を持たない ⇔ 連結成分が木 です。
また 木 ⇒ 辺の数は 頂点数 – 1 です。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); Dsu dsu = new Dsu(N); for (int i = 0; i < M; i++) { (int u, int v) = ReadInt2(); u--; v--; dsu.Merge(u, v); } foreach (var group in dsu.Groups()) M -= group.Length - 1; Console.WriteLine(M); } } |
D – Friends
問題の概要
N 人の人がいる。
「人 A[i] と人 B[i] は友達である」という情報が M 個与えられる。
X と Y が友達、かつ、Y と Z が友達ならば、X と Z も友達である。
この N 人をいくつかのグループに分け、すべての人について「同じグループの中に友達がいない」という状況を作りたい。
最小でいくつのグループに分ければ良いだろうか？
まず Union-Find で友達なら同じ連結成分に属するようにわけます。
「同じグループの中に友達がいない」という状況を作るのであれば同じ連結成分に属する人をバラバラにしなければなりませんが、そうでないなら同じグループにしても問題ありません。
なので、各連結成分の大きさの最大値が解となります。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); Dsu dsu = new Dsu(N); for (int i = 0; i < M; i++) { (int u, int v) = ReadInt2(); u--; v--; dsu.Merge(u, v); } long ans = 0; foreach (var group in dsu.Groups()) ans = Math.Max(ans, group.Length); Console.WriteLine(ans); } } |
D – Do use hexagon grid
問題の概要
無限に広い六角形のグリッドがある。最初、すべてのマスは白である。
ある六角形のマスは 2 つの整数 i, j を用いて (i, j) と表され、マス (i, j) は以下の 6 つのマスと隣接する。
(i – 1, j – 1)
(i – 1, j)
(i, j – 1)
(i, j + 1)
(i + 1, j)
(i + 1, j + 1)
N 個のマスを黒く塗ったが、黒いマスがいくつの連結成分をなすか求めよ。
六角形のマスは 2 つの整数 i, j を用いて表されるが、これを 1 つの整数で表すことができるようにすると Union-Find が使えます。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } int N = int.Parse(Console.ReadLine()); int[] X = new int[N]; int[] Y = new int[N]; Dictionary<string, int> dic = new Dictionary<string, int>(); for (int i = 0; i < N; i++) { (int x, int y) = ReadInt2(); X[i] = x; Y[i] = y; dic.Add($"{x},{y}", i); } Dsu dsu = new Dsu(N); for (int i = 0; i < N; i++) { int x = X[i]; int y = Y[i]; if (dic.ContainsKey($"{x - 1},{y - 1}")) dsu.Merge(i, dic[$"{x - 1},{y - 1}"]); if (dic.ContainsKey($"{x - 1},{y}")) dsu.Merge(i, dic[$"{x - 1},{y}"]); if (dic.ContainsKey($"{x},{y - 1}")) dsu.Merge(i, dic[$"{x},{y - 1}"]); if (dic.ContainsKey($"{x},{y + 1}")) dsu.Merge(i, dic[$"{x},{y + 1}"]); if (dic.ContainsKey($"{x + 1},{y}")) dsu.Merge(i, dic[$"{x + 1},{y}"]); if (dic.ContainsKey($"{x + 1},{y + 1}")) dsu.Merge(i, dic[$"{x + 1},{y + 1}"]); } Console.WriteLine(dsu.Groups().Length); } } |
D – New Friends
問題の概要
N 人のユーザーが利用している SNS がある。
この SNS では 2 人のユーザが互いに友達になれる機能があり、友達関係は双方向的である。
現在 SNS 上には M 組の友達関係が存在し、i 組目の友達関係はユーザー A[i] とユーザー B[i] からなる。
「X と Y は友達、Y と Z は友達であり、X と Z は友達でないようなユーザーを選んで X と Z を友達にする」という操作をおこなえる最大の回数を求めよ。
「X と Y は友達、Y と Z は友達であり、X と Z は友達でないようなユーザーを選んで X と Z を友達にする」という操作を繰り返すとその連結成分は任意の 2 頂点間に辺があるグラフになります。この場合、辺の数は連結成分に属する頂点数を n とすると n (n – 1) / 2 になります。
なので各連結成分の頂点数 n から n (n – 1) / 2 の総和を計算し、最初から存在した辺の数である M を引けばそれが解となります。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); Dsu dsu = new Dsu(N); for (int i = 0; i < M; i++) { (int a, int b) = ReadInt2(); a--; b--; dsu.Merge(a, b); } long ans = 0; foreach (var group in dsu.Groups()) ans += 1L * group.Length * (group.Length - 1) / 2; ans -= M; Console.WriteLine(ans); } } |
C – Puddles
問題の概要
縦 H 行、横 W 列のグリッドがある。
上から i 行目左から j 列目のマスは S[i, j] が ‘#’ のとき黒く ‘.’ のとき白く塗られている。
白マスの連結成分であって、グリッドの最外周のマスを含まないものの個数を求めよ。
白く塗られているマスの連結成分を考えればいいのですが、四方向が黒マスで囲まれていなければなりません。連結成分のうち端にあるマスを含まないものだけを数えればよいです。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int H, int W) = ReadInt2(); char[][] grid = new char[H][]; for (int r = 0; r < H; r++) { grid[r] = Console.ReadLine().ToArray(); } int ToIndex(int r, int c) => r * W + c; (int, int) ToRowCol(int idx) => (idx / W, idx % W); Dsu dsu = new Dsu(H * W + 1); for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (grid[r][c] == '.') { if (r - 1 >= 0 && grid[r - 1][c] == '.') dsu.Merge(ToIndex(r, c), ToIndex(r - 1, c)); if (r + 1 < H && grid[r + 1][c] == '.') dsu.Merge(ToIndex(r, c), ToIndex(r + 1, c)); if (c - 1 >= 0 && grid[r][c - 1] == '.') dsu.Merge(ToIndex(r, c), ToIndex(r, c - 1)); if (c + 1 < W && grid[r][c + 1] == '.') dsu.Merge(ToIndex(r, c), ToIndex(r, c + 1)); } else dsu.Merge(ToIndex(r, c), H * W); } } long ans = 0; foreach (var group in dsu.Groups()) { // 連結成分のうち端にあるマスが含まれていたり '#' であるものは除外する bool ok = !group.Any(_ => { var rc = ToRowCol(_); return (rc.Item1 == 0 || rc.Item1 == H - 1 || rc.Item2 == 0 || rc.Item2 == W - 1); }); if (ok) ans++; } Console.WriteLine(ans); } } |
C – Cycle Graph?
問題の概要
N 頂点 M 辺の単純無向グラフが与えられる。
このグラフがサイクルグラフであるか判定せよ。
グラフがサイクルグラフ ⇔ グラフが連結 かつ すべての頂点の次数が 2 です。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); Dsu dsu = new Dsu(N); int[] counts = new int[N]; // 頂点から出ている辺の数 for (int i = 0; i < M; i++) { (int a, int b) = ReadInt2(); a--; b--; dsu.Merge(a, b); counts[a]++; counts[b]++; } Console.WriteLine(dsu.Groups().Length == 1 && counts.All(_ => _ == 2) ? "Yes" : "No"); } } |
D – Tying Rope
問題の概要
一方の端が赤に塗られており、もう一方の端が青に塗られているロープが N 本ある。
ロープの端を結ぶ操作を M 回おこなう。
i 回目の操作ではロープ A[i] の色 B[i] の端とロープ C[i] の色 D[i] の端を結ぶ。
すべての操作を終えた後に、ひとつながりになっているロープの組について環状になっているものとそうでないものの個数を出力せよ。
N 本のロープの両端を頂点 2i, 頂点 2i + 1 とみなしてロープを結んだら頂点を merge します。連結成分の個数がひとつながりになっているロープの組の個数です。環状になっているかどうかは連結成分内の辺の数で判定できます。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); Dsu dsu = new Dsu(N * 2); int[] counts = new int[N * 2]; // 頂点から出ている辺の数 // 同じロープの両端に相当する頂点を merge する for (int i = 0; i < N; i++) { int u = i * 2; int v = i * 2 + 1; dsu.Merge(u, v); counts[u]++; counts[v]++; } for (int i = 0; i < M; i++) { string[] vs = Console.ReadLine().Split(); int a = int.Parse(vs[0]) - 1; string b = vs[1]; int c = int.Parse(vs[2]) - 1; string d = vs[3]; int u = b == "R" ? a * 2 : a * 2 + 1; int v = d == "R" ? c * 2 : c * 2 + 1; dsu.Merge(u, v); counts[u]++; counts[v]++; } int X = 0; int Y = 0; foreach (var group in dsu.Groups()) { int e_cnt = 0; foreach (var v in group) e_cnt += counts[v]; // 同じ辺を 2 回数えているので e_cnt / 2 // これが頂点数と一致するなら環状になっている if (e_cnt / 2 == group.Length) X++; else Y++; } Console.WriteLine($"{X} {Y}"); } } |
D – Unicyclic Components
問題の概要
N 頂点 M 辺の無向グラフが与えられる。
このグラフのすべての連結成分が「その連結成分に含まれる頂点の個数と辺の本数が等しい」かどうかを判定せよ。
各連結成分に属する頂点の次数の合計を半分にするとその連結成分に含まれる辺の本数がわかります。あとはその連結成分に含まれる頂点の数と辺の本数を比較するだけです。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); Dsu dsu = new Dsu(N); int[] counts = new int[N]; for (int i = 0; i < M; i++) { (int v, int u) = ReadInt2(); v--; u--; dsu.Merge(u, v); counts[u]++; counts[v]++; } bool yes = true; foreach (var group in dsu.Groups()) { int e_cnt = 0; foreach (var v in group) e_cnt += counts[v]; // 同じ辺を 2 回数えているので e_cnt / 2 // これが頂点数と一致するか？ if (e_cnt / 2 != group.Length) yes = false; } Console.WriteLine(yes ? "Yes" : "No"); } } |
D – Circumferences
問題の概要
xy 平面上の N 個の円が与えられる。
N 個の円のうち少なくとも 1 つ以上の円の円周上にある点のみを通って、点 (sx, sy) から点 (tx, ty) に行くことができるかどうかを判定せよ。
円をひとつの頂点とみなして円が他の円と接するか交わっていれば頂点を merge します。点 (sx, sy) がある円と点 (tx, ty) がある円が同一連結成分内にあれば “Yes” です。
|
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 |
using AtCoder; class Program { static void Main() { (int, int, int, int) ReadInt4() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2]), int.Parse(vs[3])); } (int, int, int) ReadInt3() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2])); } int N = int.Parse(Console.ReadLine()); (int sx, int sy, int tx, int ty) = ReadInt4(); long[] X = new long[N]; long[] Y = new long[N]; long[] R = new long[N]; int s = 0, t = 0; for (int i = 0; i < N; i++) { (int x, int y, int r) = ReadInt3(); X[i] = x; Y[i] = y; R[i] = r; long d2 = (X[i] - sx) * (X[i] - sx) + (Y[i] - sy) * (Y[i] - sy); if (d2 == R[i] * R[i]) s = i; d2 = (X[i] - tx) * (X[i] - tx) + (Y[i] - ty) * (Y[i] - ty); if (d2 == R[i] * R[i]) t = i; } Dsu dsu = new Dsu(N); for (int a = 0; a < N; a++) { for (int b = a + 1; b < N; b++) { long d2 = (X[a] - X[b]) * (X[a] - X[b]) + (Y[a] - Y[b]) * (Y[a] - Y[b]); if ((R[a] + R[b]) * (R[a] + R[b]) >= d2 && (R[a] - R[b]) * (R[a] - R[b]) <= d2) dsu.Merge(a, b); } } Console.WriteLine(dsu.Same(s, t) ? "Yes" : "No"); } } |
