ひとりで勝手にはじめた蟻本読書会 グラフ理論 木上での全頂点対最短経路問題と最小共通祖先 蟻本読書会 の続きです。今回も前回同様、木関連の自由研究です。
Contents
葉の判定
木には葉と呼ばれる特殊な頂点が必ず存在します。葉は木を図に起こした時に一番末端に現れる頂点、つまり、接続する辺が 1 本のみであるような頂点のことをいいます。例として、以下の図で赤くなっている頂点は葉になっています。
頂点に 1 ～ N の番号がついた木の頂点・辺についての情報が与えられるので、葉である全ての頂点の番号を昇順に改行区切りで出力してください。
入力されるデータ
N
a_1 b_1
a_2 b_2
…
a_{N-1} b_{N-1}（ただし、1 ≦ N ≦ 100, 1 ≦ a_i , b_i ≦ N ）
頂点 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 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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); List<int>[] list = new List<int>[N]; for (int i = 0; i < N; i++) list[i] = new List<int>(); for (int i = 0; i < N - 1; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; int b = vs[1] - 1; list[a].Add(b); list[b].Add(a); } List<int> rets = GetLeafs(N, 0, list).OrderBy(_ => _).ToList(); foreach (int ret in rets) Console.WriteLine(ret + 1); } static List<int> GetLeafs(int n, int start, List<int>[] list) { bool[] visits = new bool[n]; Queue<int> queue = new Queue<int>(); queue.Enqueue(start); visits[start] = true; List<int> rets = new List<int>(); while (queue.Count > 0) { int cur = queue.Dequeue(); if (list[cur].Count == 1) // 葉 rets.Add(cur); foreach (int next in list[cur]) { if (visits[next]) continue; visits[next] = true; queue.Enqueue(next); } } return rets; } } |
木の中心
頂点が 1 つ、または 2 つとなるまで次の操作を繰り返していき、残った頂点を（元の） 木の中心といいます。頂点に 1 ～ N の番号がついた木の頂点・辺についての情報が与えられるので、木の中心である頂点の番号を昇順に改行区切りで出力してください。
入力されるデータ
N
a_1 b_1
…
a_{N-1} b_{N-1}（ただし、1 ≦ N ≦ 100, 1 ≦ a_i, b_i ≦ N ）
GetLeafs メソッドは同じなので省略です。葉を取得したら隣接リストからその頂点を取り除きます。そしてこの処理を隣接する頂点を 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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
using System; using System.Collections.Generic; using System.Linq; class Program { // GetLeafs メソッドは同じなので省略 static void Main() { int N = int.Parse(Console.ReadLine()); List<int>[] list = new List<int>[N]; for (int i = 0; i < N; i++) list[i] = new List<int>(); for (int i = 0; i < N - 1; i++) { int[] vs = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; int b = vs[1] - 1; list[a].Add(b); list[b].Add(a); } bool[] isRemoved = new bool[N]; // 頂点は取り除されたか？ while (true) { List<int> starts = list.FirstOrDefault(_ => _.Count > 0); List<int> nodes = list.FirstOrDefault(_ => _.Count >= 2); if(nodes == null) // 隣接する頂点を 2 つ以上もつ頂点は存在しない break; List<int> leafs = GetLeafs(N, starts[0], list).OrderBy(_ => _).ToList(); foreach (int leaf in leafs) { // 隣接リストから葉を取り除く list[leaf].Clear(); foreach (List<int> li in list) li.Remove(leaf); // 葉は取り除かれた isRemoved[leaf] = true; } } for (int i = 0; i < N; i++) { if (!isRemoved[i]) Console.WriteLine(i + 1); } } } |
木の直径
ある木における、最も遠い 2 頂点間の距離をその木の直径といいます。木 T についての情報が与えられるので、T の直径の値を求めてください。
入力されるデータ
N
a_1 b_1
a_2 b_2
…
a_{N-1} b_{N-1}（ただし、1 ≦ N ≦ 100, 1 ≦ a_i , b_i ≦ N ）
最も遠い 2 頂点間の距離を求めるには、まず任意の点から最も遠い頂点を求めます。そして求められた頂点から最も遠い頂点を求めれば、最も遠い 2 頂点を取得することができます。
ある頂点から最も遠い頂点を求めるには、すべての頂点との距離を幅優先探索で求めたのち、距離が最も長い頂点を採用すればよいです。
GetDistanceメソッドは始点として定めた頂点からの全頂点の距離を取得します。
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); List<int>[] list = new List<int>[N]; for (int i = 0; i < N; i++) list[i] = new List<int>(); for (int i = 0; i < N - 1; i++) { int[] vs = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; int b = vs[1] - 1; list[a].Add(b); list[b].Add(a); } List<int> distances = GetDistance(N, 0, list).ToList(); int max = distances.Max(); int start = distances.IndexOf(max); distances = GetDistance(N, start, list).ToList(); max = distances.Max(); Console.WriteLine(max); } static int[] GetDistance(int n, int start, List<int>[] list) { bool[] visits = new bool[n]; int[] distances = new int[n]; for (int i = 0; i < n; i++) distances[i] = int.MaxValue / 2; Queue<int> queue = new Queue<int>(); queue.Enqueue(start); visits[start] = true; distances[start] = 0; while (queue.Count > 0) { int cur = queue.Dequeue(); int distance = distances[cur]; foreach (int next in list[cur]) { if (visits[next]) continue; visits[next] = true; if(distances[next] > distance + 1) distances[next] = distance + 1; queue.Enqueue(next); } } return distances; } } |
根付き木の親子関係
実際に根付き木を利用する際には、与えられた木と根の情報から自分で頂点の親子関係を求める必要があることが多いです。
根付き木の頂点・辺についての情報が与えられるので、木の全ての辺に対して、どのような親子関係になっているかを求めてください。
根の頂点を 1 つ決めると、各頂点の親子関係が定まります。根付き木の頂点の数 N, 根付き木の根の頂点番号 R が与えられます。そのあと根付き木の各辺の両端の頂点の番号 a_i , b_i が与えられます。i 行目には、a_i が b_i の親である場合は “A” を、b_i が a_i の親である場合は “B” を出力してください。
入力されるデータ
N R
a_1 b_1
…
a_{N-1} b_{N-1}ただし、1 ≦ N ≦ 100, 1 ≦ R ≦ N
1 ≦ a_i, b_i ≦ N
まずは木の全頂点について根からの距離を求めます。あとは a_i と 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 35 36 37 38 39 40 41 42 43 44 45 |
using System; using System.Collections.Generic; using System.Linq; using System.Threading; class Program { // GetDistance メソッドは同じなので省略 static void Main() { int N, R; { int[] vs = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; R = vs[1] - 1; } List<int>[] list = new List<int>[N]; for (int i = 0; i < N; i++) list[i] = new List<int>(); List<int> A = new List<int>(); List<int> B = new List<int>(); for (int i = 0; i < N - 1; i++) { int[] vs = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; int b = vs[1] - 1; list[a].Add(b); list[b].Add(a); A.Add(a); B.Add(b); } List<int> distances = GetDistance(N, R, list).ToList(); for (int i = 0; i < A.Count; i++) { if (distances[A[i]] < distances[B[i]]) Console.WriteLine("A"); else Console.WriteLine("B"); } } } |
根付き木の根を他の頂点に変更した時、根付き木の親子関係は変化します。根付き木の頂点・辺についての情報と、新たな根となる頂点の番号と K 個の頂点 v_1 … v_K が与えられるので、各頂点について親の頂点を出力してください。
入力されるデータ
N R
a_1 b_1
…
a_{N-1} b_{N-1}
K r
v_1
…
v_K（ただし、N は根付き木の頂点の数, R は根付き木の根の頂点番号
a_i , b_i は根付き木の各辺の両端の頂点番号
a_i が b_i の親であることが保証されている
r は新しい根となる頂点の番号 K はクエリの数
v_i は親の頂点を求めたい頂点の番号
1 ≦ N ≦ 100, 1 ≦ R ≦ N
1 ≦ a_i , b_i ≦ N
1 ≦ K ≦ 100, 1 ≦ r ≦ N, 1 ≦ v_i ≦ N ）
新しい根が決まったら幅優先探索をして親を取得します。GetParentsメソッド内で配列を定義し、新たに訪問する頂点に対応する要素に訪問元の頂点番号をセットしています。あとはクエリが飛んできたらGetParentsメソッドが返した配列を参照して値を出力するだけです。
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Threading; class Program { static void Main() { int N, R; { int[] vs = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; R = vs[1] - 1; } List<int>[] list = new List<int>[N]; for (int i = 0; i < N; i++) list[i] = new List<int>(); for (int i = 0; i < N - 1; i++) { int[] vs = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; int b = vs[1] - 1; list[a].Add(b); list[b].Add(a); } int K, r; { int[] vs = Console.ReadLine().Trim().Split().Select(_ => int.Parse(_)).ToArray(); K = vs[0]; r = vs[1] - 1; } List<int> parents = GetParents(N, r, list).ToList(); List<int> rets = new List<int>(); for (int i = 0; i < K; i++) { int q = int.Parse(Console.ReadLine()) - 1; rets.Add(parents[q] + 1); } foreach(int ret in rets) Console.WriteLine(ret); } static int[] GetParents(int n, int root, List<int>[] list) { bool[] visits = new bool[n]; int[] parents = new int[n]; Queue<int> queue = new Queue<int>(); queue.Enqueue(root); visits[root] = true; parents[root] = -1; while (queue.Count > 0) { int cur = queue.Dequeue(); foreach (int next in list[cur]) { if (visits[next]) continue; visits[next] = true; parents[next] = cur; queue.Enqueue(next); } } return parents; } } |
