using System; using System.Collections.Generic; using System.Linq; using System.Numerics; using Debug = System.Diagnostics.Debug; using StringBuilder = System.Text.StringBuilder; public class SuccessfulMerger { public int minimumMergers(int[] road) { var n = road.Length; var G = Enumerate(n, x => new List()); for (int i = 0; i < n; i++) { G[i].Add(road[i]); G[road[i]].Add(i); } var isCycle = new bool[n]; //閉路検出 { for (int i = 0; i < n; i++) isCycle[i] = true; var notCycle = Graph.TopologicalSort(G); foreach (var x in notCycle) isCycle[x] = false; } } static public T[] Enumerate(int n, Func f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; } } #region TopologicalSort static partial class Graph { //順序をいじりたい場合はQueueから変える //使わない奴がある場合はcountのその位置に予め-1を入れて渡す //循環してるとサイズが小さくなるはず? static public int[] TopologicalSort(List[] G, int[] count = null) { const int Capacity = 1;//有向ならば0無向ならば1 var n = G.Length; if (count == null) { count = new int[n]; foreach (var l in G) foreach (var x in l) count[x]++; } var ret = new List(); var q = new Queue(); for (int i = 0; i < n; i++) if (count[i] == Capacity) q.Enqueue(i); while (q.Any()) { var p = q.Dequeue(); ret.Add(p); foreach (var x in G[p]) if (--count[x] == Capacity) q.Enqueue(x); } return ret.ToArray(); } } #endregion