AtCoderのABC
次のABCの問題へ
前のABCの問題へ
ABC168-D .. (Double Dots)
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("4 4");
WillReturn.Add("1 2");
WillReturn.Add("2 3");
WillReturn.Add("3 4");
WillReturn.Add("4 2");
//Yes
//1
//2
//2
}
else if (InputPattern == "Input2") {
WillReturn.Add("6 9");
WillReturn.Add("3 4");
WillReturn.Add("6 1");
WillReturn.Add("2 4");
WillReturn.Add("5 3");
WillReturn.Add("4 6");
WillReturn.Add("1 5");
WillReturn.Add("6 2");
WillReturn.Add("4 5");
WillReturn.Add("5 6");
//Yes
//6
//5
//5
//1
//1
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
int N = wkArr[0];
// 隣接リスト
var ToNodeListDict = new Dictionary<int, List<int>>();
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray();
foreach (string EachStr in InputList.Skip(1)) {
SplitAct(EachStr);
int A = wkArr[0];
int B = wkArr[1];
Action<int, int> AddAct = (pFrom, pTo) =>
{
if (ToNodeListDict.ContainsKey(pFrom) == false) {
ToNodeListDict[pFrom] = new List<int>();
}
ToNodeListDict[pFrom].Add(pTo);
};
AddAct(A, B);
AddAct(B, A);
}
var Que = new Queue<int>();
Que.Enqueue(1);
var AnswerDict = new Dictionary<int, int>();
var VisitedSet = new HashSet<int>();
VisitedSet.Add(1);
while (Que.Count > 0) {
int Dequeued = Que.Dequeue();
foreach (int EachInt in ToNodeListDict[Dequeued]) {
//再訪禁止
if (VisitedSet.Add(EachInt) == false) {
continue;
}
Que.Enqueue(EachInt);
AnswerDict[EachInt] = Dequeued;
}
}
Console.WriteLine("Yes");
for (int I = 2; I <= N; I++) {
Console.WriteLine(AnswerDict[I]);
}
}
}
解説
連結グラフなので
全ての頂点は、頂点1から到達可能です。
BFSで、直前の訪問ノードが、ノードごとの解になります。