AtCoder NoviStepsを埋めてみる(28) 幅優先探索 1Dの続きです。今回はサイクル検出です。
C – Find it!
問題の概要
N 頂点 N 辺の有向グラフがあたえられる。
同一頂点を複数回含まない有向閉路をひとつ求めよ。
深さ優先探索で全経路探索をします。再帰関数の引数に現在訪問中の頂点を渡して Stack に Push し、関数が終了したら Pop します。これで全経路探索できます。Stack に格納されている頂点に再度訪問したらそこに閉路があることになります。そのときは Stack の後ろからその頂点があるところまで切り出せば、それが求める閉路となります（後ろから取り出すのでこのままだと順番が逆になるので注意）。
ただし一度探索して閉路を発見することができなかった頂点よりも向こう側を探索しても時間の無駄なので、一度探索した頂点は訪問済みフラグを設定して何度も探索しないようにします。
|
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 |
class Program { // 最初にみつけた閉路を返す static List<int> GetFirstCycle(List<int>[] G) { int v_cnt = G.Length; bool[] contains = new bool[v_cnt]; bool[] seen = new bool[v_cnt]; Stack<int> path = new Stack<int>(); List<int> res = new List<int>(); for (int i = 0; i < v_cnt; i++) { if (!seen[i]) { Dfs(i); if (res.Count > 0) return res; } } return res; void Dfs(int cur) { if (contains[cur] && res.Count == 0) { List<int> vs = path.Reverse().ToList(); int idx = vs.IndexOf(cur); res = vs.Skip(idx).ToList(); return; } if (seen[cur] || res.Count > 0) return; contains[cur] = true; seen[cur] = true; path.Push(cur); foreach (int next in G[cur]) Dfs(next); path.Pop(); contains[cur] = false; } } static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); // 各頂点の出次数が 1 なのでリストの配列にする必要はないのだが汎用性を重視して・・・ List<int>[] G = new List<int>[N]; for (int i = 0; i < N; i++) { G[i] = new List<int>(); G[i].Add(A[i] - 1); } List<int> res = GetFirstCycle(G); res = res.Select(_ => _ + 1).ToList(); Console.WriteLine(res.Count); Console.WriteLine(string.Join(" ", res)); } } |
D – Teleporter
問題の概要
N 個の町があり、それぞれの町にはテレポーターが 1 台ずつ設置されている。町 i のテレポーターの転送先は町 A[i] である。
町 1 から出発してテレポーターをちょうど K 回使うと、どの町に到着するかを求めよ。
K が大きな数なのですが、テレポートを繰り返すことで必ずどこかで同じ街を巡回することになります。有向グラフを構築すると必ず閉路ができます。（K – 閉路までの距離 % 閉路長）から閉路のどの部分で止まるかがわかります。与えられた K が小さい場合、閉路にたどり着けない場合があるので注意が必要です。
|
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 |
class Program { // 最初にみつけた閉路と閉路よりも前のパスを返す static (List<int> Cycle, List<int> PreCycle) GetFirstCycle(List<int>[] G, int start) { int v_cnt = G.Length; bool[] contains = new bool[v_cnt]; bool[] seen = new bool[v_cnt]; Stack<int> path = new Stack<int>(); List<int> cycle = new List<int>(); List<int> pre_cycle = new List<int>(); Dfs(start); return (cycle, pre_cycle); void Dfs(int cur) { if (contains[cur] && cycle.Count == 0) { List<int> vs = path.Reverse().ToList(); int idx = vs.IndexOf(cur); cycle = vs.Skip(idx).ToList(); pre_cycle = vs.Take(idx).ToList(); return; } if (seen[cur] || cycle.Count > 0) return; contains[cur] = true; seen[cur] = true; path.Push(cur); foreach (int next in G[cur]) Dfs(next); path.Pop(); contains[cur] = false; } } static void Main() { string[] nk = Console.ReadLine().Split(); int N = int.Parse(nk[0]); long K = long.Parse(nk[1]); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); List<int>[] G = new List<int>[N]; for (int i = 0; i < N; i++) { G[i] = new List<int>(); G[i].Add(A[i] - 1); } var res = GetFirstCycle(G, 0); if (K >= res.PreCycle.Count) { int idx = (int)((K - res.PreCycle.Count) % res.Cycle.Count); Console.WriteLine(res.Cycle[idx] + 1); } else { int idx = (int)K; Console.WriteLine(res.PreCycle[idx] + 1); } } } |
D – Change Usernames
問題の概要
N 人のユーザがいて i 番目のユーザの現在のユーザー名は S[i] である。
すべてのユーザーは S[i] から T[i] へのユーザー名変更を希望している。
ユーザ名を変更する順序を適切に定めることで、以下の条件を全て満たすように、すべてのユーザーのユーザー名を希望通り変更することができるか判定せよ。
（条件）
ユーザ名の変更は 1 人ずつおこなう。
どのユーザーもユーザー名の変更は一度だけおこなうものとする。
ユーザー名の変更を試みる時点で他のユーザーが使っているユーザー名に変更することはできない。
すべての S[i] と T[i] が書かれた頂点（ただし S[i] == T[j] であるものがあれば同じ頂点とする）を用意します。そして S[i] から T[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 |
class Program { // GetFirstCycle(List<int>[] G) メソッドは上記定義のとおり static void Main() { int N = int.Parse(Console.ReadLine()); string[] S = new string[N]; string[] T = new string[N]; HashSet<string> set = new HashSet<string>(); for (int i = 0; i < N; i++) { string[] vs = Console.ReadLine().Split(); S[i] = vs[0]; T[i] = vs[1]; set.Add(vs[0]); set.Add(vs[1]); } string[] arr = set.ToArray(); Dictionary<string, int> stringToInt = new Dictionary<string, int>(); for (int i = 0; i < arr.Length; i++) stringToInt.Add(arr[i], i); List<int>[] G = new List<int>[arr.Length]; for (int i = 0; i < arr.Length; i++) G[i] = new List<int>(); for (int i = 0; i < N; i++) G[stringToInt[S[i]]].Add(stringToInt[T[i]]); var res = GetFirstCycle(G); Console.WriteLine(res.Count == 0 ? "Yes" : "No"); } } |
C – Repsept
問題の概要
7, 77, 777, … という数列の中に初めて K の倍数が登場するのは何項目か求めよ。
頂点番号 0 から K – 1 までの K 個の頂点を用意します。頂点番号は現在の値を K で割ったときの余りを表しています。
7 をひとつも追加していないときの数は 0 です。頂点 0 から有向辺をたどることで 頂点 0 へ戻ってくることができるなら数列のなかに K の倍数は存在し、その閉路長が求めるべき解です。戻ってこれないときは -1 が解です。これは自作メソッドの戻り値 Cycle.Count と PreCycle.Count をみればわかります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Program { // GetFirstCycle(List<int>[] G, int) メソッドは上記定義のとおり static void Main() { int K = int.Parse(Console.ReadLine()); List<int>[] G = new List<int>[K]; for (int i = 0; i < K; i++) { int next = (i * 10 + 7) % K; G[i] = new List<int>(); G[i].Add(next); } var res = GetFirstCycle(G, 0); int ans = res.PreCycle.Count == 0 ? res.Cycle.Count : -1; Console.WriteLine(ans); } } |
058 – Original Calculator（★4）
問題の概要
整数 N と K が与えられる。
x = N とし、以下の操作を K 回繰り返す。そのときの x の値を求めよ。
（操作）
整数 x を十進法で表したときの各桁の和を計算し y とする。
x + y を 10^5 で割ったあまりを z とする。
x を z に変更する。
10^5 個の頂点を用意します。あとは D_Teleporter と同じような問題です。
|
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 |
class Program { // GetFirstCycle(List<int>[] G, int) メソッドは上記定義のとおり static void Main() { string[] nk = Console.ReadLine().Split(); int N = int.Parse(nk[0]); long K = long.Parse(nk[1]); int v_cnt = 100000; List<int>[] G = new List<int>[v_cnt]; for (int i = 0; i < v_cnt; i++) { string s = i.ToString(); int y = 0; foreach (char ch in s) y += ch - '0'; int z = (i + y) % v_cnt; G[i] = new List<int>(); G[i].Add(z); } var res = GetFirstCycle(G, N); if (K >= res.PreCycle.Count) { long k = K; k -= res.PreCycle.Count; int idx = (int)(k % res.Cycle.Count); Console.WriteLine(res.Cycle[idx]); } else { int k = (int)K; Console.WriteLine(res.PreCycle[k]); } } } |
D – Moving Piece
問題の概要
N マスから成るマス目の上で、コマを使ってゲームを行おうとしています。ゲーム開始時のスコアは 0 である。
マス i には整数 C[i] が書かれていて、1, 2, …, N の順列 P が与えられる。
最初に好きなマスを 1 つ選んでコマを 1 つ置き、1 回以上 K 回以下の好きな回数だけ、次のような方法でコマを移動させる。ゲーム終了時のスコアとしてあり得る値の最大値を求めよ。
（操作）
コマがマス i にあるなら、コマをマス P[i] に移動させる。このとき、スコアに C[P[i]] が加算される。
移動先は 1, 2, …, N の順列なのでどのマスから移動を開始しても必ず元のマスに戻ってくることができます。つまり閉路になっています。
どのマスからゲームを開始するかすべて試します。移動回数は 1 回以上 K 回以下なのでスコアが最大になるタイミングでやめなければなりませんが、やめるタイミングは以下のようにして決めます。
① K が閉路長以下の場合
この場合は実際に K 回移動させてみてそのなかからスコアが最大になるものをとります。
② K が閉路長より大きく、閉路を一周して獲得できるスコアが負数の場合
閉路を回り続けてもスコアが悪化するだけなので、閉路を一周しない最大回数だけ実際に移動させて、スコアが最大になるものをとります。
③ K が閉路長より大きく、閉路を一周して獲得できるスコアが 0 以上の場合
可能な限り回ったあと、それより 0 手前から（閉路長）前まででやめる場合を考えてそのなかからスコアが最大になるものをとります。何周できるかは (K / 閉路長)を計算すればわかるし、最後の位置も閉路の (K % 閉路長)からわかります。
（閉路を一周して獲得できるスコア） × (K / 閉路長) + (閉路の先頭から (K % 閉路長) 個の総和) を計算して 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 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 |
class Program { static void Main() { int[] nk = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nk[0]; int K = nk[1]; int[] P = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] C = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); P = P.Select(_ => _ - 1).ToArray(); long ans = long.MinValue; for (int i = 0; i < N; i++) { ans = Math.Max(ans, Solve(i)); } Console.WriteLine(ans); // 頂点 i を起点に巡回したときのスコアをそれぞれ計算する long Solve(int start) { int v = start; List<int> cycle = new List<int>(); // 閉路を構成する頂点を取得する while (true) { cycle.Add(v); v = P[v]; if (v == start) break; } // 1 周したときの頂点数とスコアを計算する long cycle_sum = 0; foreach (var idx in cycle) cycle_sum += C[idx]; long max = long.MinValue; if (K <= cycle.Count) { // K が閉路長以下の場合 // K 回シミュレーションして最大スコアをとる long sum = 0; for (int i = 0; i < K; i++) { int idx = cycle[i]; sum += C[idx]; max = Math.Max(max, sum); } return max; } else if (cycle_sum < 0) { // 閉路のスコアが負数の場合 // 閉路を回り続けてもスコアが悪化するだけなので閉路長 回だけシミュレーションして最大スコアをとる long sum = 0; for (int i = 0; i < cycle.Count; i++) { int idx = cycle[i]; sum += C[idx]; max = Math.Max(max, sum); } return max; } else { // それ以外の場合 // 可能な限り回ったあと最後の1周のなかでどこでやめた場合がスコア最大になるか調べる int k = K % cycle.Count; long sum = cycle_sum * (K / cycle.Count); for (int i = 0; i < k; i++) { int idx = cycle[i]; sum += C[idx]; } max = Math.Max(max, sum); for (int i = 0; i < cycle.Count; i++) { int idx = cycle[i]; sum -= C[idx]; max = Math.Max(max, sum); } return max; } } } } |
E – Sequence Sum
問題の概要
A[0] = X, A[n + 1] = (A[n] * A[n]) % M と定義する。
A[0] から A[N – 1] までの総和を求めよ。
M 個の頂点を用意します。頂点番号は現在の値を M で割ったときの余りを表しています。
頂点 i から頂点 (i * i) % M へ有向辺を張ります。するとどの頂点から探索を開始しても必ず閉路になっています。頂点 X から閉路までの頂点番号の総和、閉路を構成する頂点番号の総和などから A[0] から A[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 |
class Program { // GetFirstCycle(List<int>[] G, int) メソッドは上記定義のとおり static void Main() { string[] nxm = Console.ReadLine().Split(); long N = long.Parse(nxm[0]); int X = int.Parse(nxm[1]); int M = int.Parse(nxm[2]); List<int>[] G = new List<int>[M]; for (int i = 0; i < M; i++) { long next = i; next = (next * next) % M; G[i] = new List<int>(); G[i].Add((int)next); } var res = GetFirstCycle(G, X); if (N <= res.PreCycle.Count) { int n = (int)N; long ans = res.PreCycle.Take(n).Select(_ => (long)_).Sum(); Console.WriteLine(ans); } else { long sum1 = res.PreCycle.Select(_ => (long)_).Sum(); long n = N - res.PreCycle.Count; long cnt = n / res.Cycle.Count; long sum2 = res.Cycle.Select(_ => (long)_).Sum() * cnt; int r = (int)(n % res.Cycle.Count); long sum3 = res.Cycle.Take(r).Select(_ => (long)_).Sum(); Console.WriteLine(sum1 + sum2 + sum3); } } } |
D – へんてこ辞書
数列 B が与えられる。頂点 i から 頂点 B[i] へ有向辺が張られているグラフ上で頂点 a を始点として N 回移動した場合、最終位置はどの頂点になるか求めよ。
似たような問題がこれまでにもありましたが、この問題は N が非常に大きい（10 の 100000乗）です。
そんなあなたに BigInteger。こんなインチキ臭いコードでも通ってしまいます。
|
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 System.Numerics; class Program { // GetFirstCycle(List<int>[] G, int) メソッドは上記定義のとおり static void Main() { int[] na = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = na[0]; int a = na[1]; BigInteger K = BigInteger.Parse(Console.ReadLine()); int[] B = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); List<int>[] G = new List<int>[N]; for (int i = 0; i < N; i++) { G[i] = new List<int>(); G[i].Add(B[i] - 1); } var res = GetFirstCycle(G, a - 1); if (K >= res.PreCycle.Count) { int idx = (int)((K - res.PreCycle.Count) % res.Cycle.Count); Console.WriteLine(res.Cycle[idx] + 1); } else { int idx = (int)K; Console.WriteLine(res.PreCycle[idx] + 1); } } } |
E – Endless Holidays
問題の概要
N 個の都市と、それぞれの都市同士を双方向に結ぶ M 本の道路がある。
この国では 一週間は W 日であり、都市ごとにいくつかの曜日が休日となっている。
曜日 1 の日の昼に、好きな都市を選んでそこを訪問し、それ以降毎日、今いる都市にとどまるか、道路で直接結ばれた都市のいずれかに移動することを繰り返す場合、現在滞在している都市が休日であるような移動を続けることが可能かどうか判定せよ。
N × W 個の頂点を用意します。i × W + w 番目の頂点が現在位置が 都市 i であり、現在日が w 曜日であることを表しています。
移動可能であれば頂点から頂点へ辺を張ります。
w 曜日の都市 u と翌日である (w + 1) % W 曜日の都市 v の両方が休日であるなら、頂点 u × W + w から v × W + ((w + 1) % W) へ有向辺を張ります。
あとは閉路があるか調べます。辺を張るときに 曜日 0 → 曜日 1 → → 曜日 W – 1 → 曜日 0 と張ったので、閉路があるなら必ず 曜日 0 のどこかの都市を含んでいます。閉路にそって移動すれば毎日が休日となります。
|
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 |
class Program { // GetFirstCycle(List<int>[] G) メソッドは上記定義のとおり static void Main() { int T = int.Parse(Console.ReadLine()); List<string> ans = new List<string>(); for (int i = 0; i < T; i++) ans.Add(Solve() ? "Yes" : "No"); foreach (var str in ans) Console.WriteLine(str); bool Solve() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; List<int> U = new List<int>(); // どの街から List<int> V = new List<int>(); // どの街へ for (int i = 0; i < M; i++) { int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); U.Add(uv[0] - 1); V.Add(uv[1] - 1); U.Add(uv[1] - 1); V.Add(uv[0] - 1); } for (int i = 0; i < N; i++) // 同じ街にとどまる { U.Add(i); V.Add(i); } int W = int.Parse(Console.ReadLine()); bool[,] mat = new bool[N, W]; for (int r = 0; r < N; r++) { string s = Console.ReadLine(); for (int c = 0; c < W; c++) mat[r, c] = s[c] == 'o'; } List<int>[] G = new List<int>[N * W]; for (int i = 0; i < N * W; i++) G[i] = new List<int>(); for (int w = 0; w < W; w++) { for (int i = 0; i < U.Count; i++) { if (mat[U[i], w] && mat[V[i], (w + 1) % W]) G[U[i] * W + w].Add(V[i] * W + ((w + 1) % W)); } } return GetFirstCycle(G).Count > 0; } } } |
E – Odd Cycle
問題の概要
N 頂点 M 辺の単純連結無向グラフが与えられる。
閉路長が 3 以上の奇数である閉路があるならひとつ示せ。
C – Find it! の自作メソッドを少し変えて Stack に格納されている頂点に番号をつけます。番号は探索開始点からの距離です。つぎに訪問しようとした頂点にすでに番号がつけられていて、差が奇数であれば、そこに奇閉路が存在することになります。
|
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 |
class Program { // 最初にみつけた奇数長の閉路を返す static List<int> GetFirstOddCycle(List<int>[] G) { int v_cnt = G.Length; int[] dists = new int[v_cnt]; bool[] seen = new bool[v_cnt]; List<int> res = new List<int>(); Stack<int> path = new Stack<int>(); Array.Fill(dists, -1); dists[0] = 0; Dfs(0, 0); return res; void Dfs(int cur, int dist) { if (dists[cur] != -1 && (dists[cur] - dist) % 2 != 0 && res.Count == 0) { List<int> vs = path.Reverse().ToList(); int idx = vs.IndexOf(cur); res = vs.Skip(idx).ToList(); return; } if (seen[cur] || res.Count > 0) return; dists[cur] = dist; seen[cur] = true; path.Push(cur); foreach (int next in G[cur]) Dfs(next, dist + 1); path.Pop(); dists[cur] = -1; } } static void Main() { int T = int.Parse(Console.ReadLine()); List<List<int>> ans = new List<List<int>>(); for (int i = 0; i < T; i++) { List<int> res = Solve(); ans.Add(res); } foreach (List<int> list in ans) { if (list.Count > 0) { Console.WriteLine(list.Count); Console.WriteLine(string.Join(" ", list)); } else Console.WriteLine(-1); } List<int> Solve() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; List<int>[] G = new List<int>[N]; for (int i = 0; i < N; i++) G[i] = new List<int>(); for (int i = 0; i < M; i++) { int[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = ab[0] - 1; int b = ab[1] - 1; G[a].Add(b); G[b].Add(a); } List<int> cycle = GetFirstOddCycle(G); return cycle.Select(_ => _ + 1).ToList(); } } } |
F – Well-defined Path Queries on a Namori
F – Well-defined Path Queries on a Namori
問題の概要
N 頂点 N 辺の連結な単純無向グラフ G が与えられる。
以下の Q 個のクエリに答えよ。
クエリ：頂点 x[i] から頂点 y[i] に向かう単純パス（同じ頂点を 2 度通らないパス）が一意に定まるか判定せよ。
N 頂点 N 辺の連結な単純無向グラフは木に辺を 1 本だけ追加したグラフと同じです。なので閉路をひとつだけ持ちます。頂点 x[i] から頂点 y[i] に向かう単純パスのなかに閉路を構成する辺が含まれるのであれば、その単純パスは一意に定まりません。なぜなら単純パスのなかに含まれる閉路を構成する辺は右回りのものであってもよいし、左回りのものであってもよいからです。
そこで閉路を構成する辺を削除したグラフを考えます。このグラフにおいて頂点 x[i] から頂点 y[i] に向かう単純パスが存在するなら “Yes” が答えでありそうでないなら “No” が答えです。頂点 x[i] から頂点 y[i] に向かう単純パスが存在するかどうかは Union-Find をつかって x[i] と y[i] が同一連結成分に属するかを調べればよいです。
閉路をひとつしか持たないグラフの閉路を構成する頂点を取得するのであれば、無向グラフであれば次数が 1 の頂点とここへ伸びる辺を取り除く、有向グラフであれば入次数が 0 の頂点とここから伸びる辺を取り除くことを繰り返して閉路を構成する頂点集合を取得する方法もあります。
|
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 91 |
using AtCoder; class Program { // 閉路をひとつしか持たないグラフの閉路を構成する頂点を取得する static HashSet<int> GetUniqueCycle(List<int>[] G) { HashSet<int> res = new HashSet<int>(); int N = G.Length; int[] counts = new int[N]; // 次数 for (int i = 0; i < N; i++) counts[i] = G[i].Count; Queue<int> q = new Queue<int>(); bool[] removed = new bool[N]; for (int i = 0; i < N; i++) { if (counts[i] == 1) { q.Enqueue(i); removed[i] = true; } } while (q.Count > 0) { int cur = q.Dequeue(); foreach (int next in G[cur]) { counts[next]--; if (counts[next] == 1) { q.Enqueue(next); removed[next] = true; } } } for (int i = 0; i < N; i++) { if (!removed[i]) res.Add(i); } return res; } static void Main() { int N = int.Parse(Console.ReadLine()); List<int>[] G = new List<int>[N]; for (int i = 0; i < N; i++) G[i] = new List<int>(); for (int i = 0; i < N; i++) { string[] uv = Console.ReadLine().Split(); int u = int.Parse(uv[0]) - 1; int v = int.Parse(uv[1]) - 1; G[u].Add(v); G[v].Add(u); } HashSet<int> cycle_set = GetUniqueCycle(G); Dsu dsu = new Dsu(N); for (int i = 0; i < N; i++) { foreach (var next in G[i]) { if (cycle_set.Contains(i) && cycle_set.Contains(next)) continue; dsu.Merge(i, next); } } int Q = int.Parse(Console.ReadLine()); List<string> ans = new List<string>(); for (int i = 0; i < Q; i++) { string[] xy = Console.ReadLine().Split(); int x = int.Parse(xy[0]) - 1; int y = int.Parse(xy[1]) - 1; ans.Add(dsu.Same(x, y) ? "Yes" : "No"); } foreach (var str in ans) Console.WriteLine(str); } } |
