AtCoderのABC
次のABCの問題へ
前のABCの問題へ
ABC329-F Colored Ball
C#のソース
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("6 5");
WillReturn.Add("1 1 1 2 2 3");
WillReturn.Add("1 2");
WillReturn.Add("6 4");
WillReturn.Add("5 1");
WillReturn.Add("3 6");
WillReturn.Add("4 6");
//1
//2
//1
//1
//3
}
else if (InputPattern == "Input2") {
WillReturn.Add("5 3");
WillReturn.Add("2 4 2 4 2");
WillReturn.Add("3 1");
WillReturn.Add("2 5");
WillReturn.Add("3 2");
//1
//2
//0
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();
SplitAct(InputList[0]);
int N = wkArr[0];
int[] CArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();
HashSet<int>[] HashArr = new HashSet<int>[N + 10];
for (int I = 0; I <= CArr.GetUpperBound(0); I++) {
HashArr[I + 1] = new HashSet<int>();
HashArr[I + 1].Add(CArr[I]);
}
var sb = new System.Text.StringBuilder();
foreach (string EachStr in InputList.Skip(2)) {
SplitAct(EachStr);
int Box1 = wkArr[0];
int Box2 = wkArr[1];
HashSet<int> SmallHashSet = HashArr[Box1];
HashSet<int> LargeHashSet = HashArr[Box2];
if (HashArr[Box1].Count > HashArr[Box2].Count) {
SmallHashSet = HashArr[Box2];
LargeHashSet = HashArr[Box1];
}
LargeHashSet.UnionWith(SmallHashSet);
HashArr[Box2] = LargeHashSet;
HashArr[Box1] = new HashSet<int>();
sb.Append(HashArr[Box2].Count);
sb.AppendLine();
}
Console.Write(sb.ToString());
}
}
解説
HashSetのUnionWithは、
要素数の少ない集合から
要素数の多い集合にコピーするほうが
高速なので、要素数を比較するようにしてます。