using System; using System.Collections.Generic; using System.Linq; // https://yukicoder.me/problems/no/2563 class Program { static string InputPattern = "InputX"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("5 6"); WillReturn.Add("1 2 2 2 1"); WillReturn.Add("1 2"); WillReturn.Add("1 3"); WillReturn.Add("1 4"); WillReturn.Add("3 4"); WillReturn.Add("4 5"); WillReturn.Add("2 5"); //2 } else if (InputPattern == "Input2") { WillReturn.Add("4 2"); WillReturn.Add("1 1 2 4"); WillReturn.Add("1 2"); WillReturn.Add("1 3"); //0 } else if (InputPattern == "Input3") { WillReturn.Add("8 9"); WillReturn.Add("1 8 1 2 1 3 3 2"); WillReturn.Add("6 3"); WillReturn.Add("3 2"); WillReturn.Add("4 3"); WillReturn.Add("5 7"); WillReturn.Add("7 3"); WillReturn.Add("2 7"); WillReturn.Add("2 1"); WillReturn.Add("1 4"); WillReturn.Add("4 7"); //4 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } static void Main() { List InputList = GetInputList(); long[] wkArr = { }; Action SplitAct = pStr => wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray(); SplitAct(InputList[0]); long NodeCnt = wkArr[0]; var InsUnionFind = new UnionFind(); for (long I = 1; I <= NodeCnt; I++) { InsUnionFind.MakeSet(I); } long[] CArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray(); // ノード色[ノード]なDict var ColorDict = new Dictionary(); // ノードのList[色]なDict var NodeListDict = new Dictionary>(); for (long I = 0; I <= CArr.GetUpperBound(0); I++) { long CurrColor = CArr[I]; ColorDict[I + 1] = CurrColor; if (NodeListDict.ContainsKey(CurrColor) == false) { NodeListDict[CurrColor] = new List(); } NodeListDict[CurrColor].Add(I + 1); } foreach (string EachStr in InputList.Skip(2)) { SplitAct(EachStr); long FromNode = wkArr[0]; long ToNode = wkArr[1]; if (ColorDict[FromNode] == ColorDict[ToNode]) { InsUnionFind.Unite(FromNode, ToNode); } } long Answer = 0; foreach (long EachColor in NodeListDict.Keys) { long FirstNode = NodeListDict[EachColor][0]; for (int I = 1; I <= NodeListDict[EachColor].Count - 1; I++) { long Root1 = InsUnionFind.FindSet(FirstNode); long Root2 = InsUnionFind.FindSet(NodeListDict[EachColor][I]); if (Root1 != Root2) { Answer++; InsUnionFind.Unite(Root1, Root2); } } } Console.WriteLine(Answer); } } #region UnionFind // UnionFindクラス internal class UnionFind { private class NodeInfoDef { internal long ParentNode; internal long Rank; } private Dictionary mNodeInfoDict = new Dictionary(); // 要素が1つである木を森に追加 internal void MakeSet(long pNode) { NodeInfoDef WillAdd = new NodeInfoDef(); WillAdd.ParentNode = pNode; WillAdd.Rank = 0; mNodeInfoDict[pNode] = WillAdd; } // 合併処理 internal void Unite(long pX, long pY) { long XNode = FindSet(pX); long YNode = FindSet(pY); long XRank = mNodeInfoDict[XNode].Rank; long YRank = mNodeInfoDict[YNode].Rank; if (XRank > YRank) { mNodeInfoDict[YNode].ParentNode = XNode; } else { mNodeInfoDict[XNode].ParentNode = YNode; if (XRank == YRank) { mNodeInfoDict[YNode].Rank++; } } } // ノードを引数として、木の根を取得 internal long FindSet(long pTargetNode) { // 根までの経路上のノードのList var PathNodeList = new List(); long CurrNode = pTargetNode; while (CurrNode != mNodeInfoDict[CurrNode].ParentNode) { PathNodeList.Add(CurrNode); CurrNode = mNodeInfoDict[CurrNode].ParentNode; } // 経路圧縮 (親ポインタの付け替え) foreach (long EachPathNode in PathNodeList) { mNodeInfoDict[EachPathNode].ParentNode = CurrNode; } return CurrNode; } internal void DebugPrint() { foreach (var EachPair in mNodeInfoDict.OrderBy(pX => pX.Key)) { Console.WriteLine("mNodeInfoDict[{0}].ParentNode={1}", EachPair.Key, EachPair.Value.ParentNode); } } } #endregion