結果
問題 |
No.2563 色ごとのグループ
|
ユーザー |
![]() |
提出日時 | 2025-02-20 21:49:57 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 866 ms / 2,000 ms |
コード長 | 5,302 bytes |
コンパイル時間 | 3,138 ms |
コンパイル使用メモリ | 117,740 KB |
実行使用メモリ | 96,980 KB |
最終ジャッジ日時 | 2025-02-20 21:50:14 |
合計ジャッジ時間 | 16,485 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections.Generic; using System.Linq; // https://yukicoder.me/problems/no/2563 class Program { static string InputPattern = "InputX"; static List<string> GetInputList() { var WillReturn = new List<string>(); 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<string> InputList = GetInputList(); long[] wkArr = { }; Action<string> 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<long, long>(); // ノードのList[色]なDict var NodeListDict = new Dictionary<long, List<long>>(); 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<long>(); } 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<long, NodeInfoDef> mNodeInfoDict = new Dictionary<long, NodeInfoDef>(); // 要素が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>(); 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