AtCoder NoviStepsを埋めてみる(13) Union-Find 2Q以下の続きです。今回は Union-Find で二部グラフ判定の処理をおこないます。
047 – Bipartite Graph
問題の概要
頂点数が N、辺の数が M のグラフが与えられる。
このグラフが二部グラフであるかどうか判定せよ。
Union-Find は二部グラフ判定にも使えます。
まず 2 N 個 の頂点を用意します。そして 頂点 u と v が辺でつながっているときは u と N + v、N + u と v をそれぞれ merge します。
頂点 u と 頂点 N + u が対応していて、u は グラフ上の頂点 u を白で塗ること、N + u は グラフ上の頂点 u を黒で塗ることを意味しています。u と N + v を merge するのは頂点 u が白なら v は黒、N + u と v を merge するのは u が黒なら v は白 を意味します。
最後に矛盾がないか確認します。頂点 u と 頂点 N + u が同じ連結成分だとグラフ上の頂点 u を白で塗ることと黒で塗ることが同時に起きることになるので矛盾しています。このような矛盾がなければそのグラフは二部グラフです。
|
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 |
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); for (int i = 0; i < M; i++) { (int a, int b) = ReadInt2(); a--; b--; dsu.Merge(a, b + N); dsu.Merge(a + N, b); } bool yes = true; for (int i = 0; i < N; i++) { if (dsu.Same(i, i + N)) yes = false; } Console.WriteLine(yes ? "Yes" : "No"); } } |
026 – Independent Set on a Tree（★4）
026 – Independent Set on a Tree（★4）
問題の概要
N 頂点の木が与えられる。
この木からどの頂点も隣り合わないように、重複しない N / 2 個の頂点の番号を出力せよ。
木は二部グラフなので隣り合う頂点を異なる色（白 or 黒）を塗り分けることができます。白か黒のどちらかは必ず N / 2 個以上あるので、そのなかから N / 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 30 31 32 33 34 35 |
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()); Dsu dsu = new Dsu(N * 2); for (int i = 0; i < N - 1; i++) { (int a, int b) = ReadInt2(); a--; b--; dsu.Merge(a, b + N); dsu.Merge(a + N, b); } foreach (var group in dsu.Groups()) { int[] arr = group.Where(_ => _ < N).ToArray(); if (arr.Length >= N / 2) { Console.WriteLine(string.Join(" ", arr.Take(N / 2).OrderBy(_ => _).Select(_ => _ + 1))); return; } } } } |
D – Good Tuple Problem
問題の概要
N 以下の正整数からなる長さ M の数列の組 (A, B) が与えられる。
0, 1 からなる長さ N の数列 X であって次の条件を満たすものが存在するか判定せよ。
[条件] i = 1, 2, …, M それぞれについて、X[A[i]] ≠ X[B[i]] が成立する。
これは N 頂点 M 辺のグラフを構築したとき 頂点 A[i] と 頂点 B[i] に白と黒で異なる色（X[A[i]] ≠ X[B[i]]）を塗ることができるかを判定するのと同じことです。要は二部グラフ判定問題です。
|
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 |
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(); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] B = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); Dsu dsu = new Dsu(N * 2); for (int i = 0; i < M; i++) { int a = A[i] - 1; int b = B[i] - 1; dsu.Merge(a, b + N); dsu.Merge(a + N, b); } bool yes = true; for (int i = 0; i < N; i++) { if (dsu.Same(i, N + i)) yes = false; } Console.WriteLine(yes ? "Yes" : "No"); } } |
D – Collision
問題の概要
N 頂点の木がある。
Q 個のクエリが与えられます。
頂点 A には 駒αが、頂点 B には 駒β が置かれていて
駒αは B へ、駒βは A に向かって最短経路で同じ速度で移動する。
両者が同じ頂点で出会うことはあるだろうか？ それとも辺上ですれ違うことになるだろうか？
木なので二部グラフであり、各頂点をふたつの色で塗り分けることができます。αとβの移動開始点が同じ色の頂点の場合は同じ頂点で出会うことになります。そうでない場合は辺ですれ違うことになります。
|
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 |
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 Q) = ReadInt2(); Dsu dsu = new Dsu(N * 2); for (int i = 0; i < N - 1; i++) { (int a, int b) = ReadInt2(); a--; b--; dsu.Merge(a, b + N); dsu.Merge(a + N, b); } for (int i = 0; i < Q; i++) { (int c, int d) = ReadInt2(); c--; d--; Console.WriteLine(dsu.Same(c, d) ? "Town" : "Road"); } } } |
