AtCoderのABC
次のABCの問題へ
前のABCの問題へ
ABC126-D Even Relation
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("3");
WillReturn.Add("1 2 2");
WillReturn.Add("2 3 1");
//0
//0
//1
}
else if (InputPattern == "Input2") {
WillReturn.Add("5");
WillReturn.Add("2 5 2");
WillReturn.Add("2 3 10");
WillReturn.Add("1 3 8");
WillReturn.Add("3 4 2");
//1
//0
//1
//0
//1
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
struct NodeInfoDef
{
internal long ToNode;
internal long Cost;
}
// 隣接リスト
static Dictionary<long, List<NodeInfoDef>> mToNodeListDict =
new Dictionary<long, List<NodeInfoDef>>();
struct JyoutaiDef
{
internal long CurrNode;
internal long CostSum;
}
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
long N = long.Parse(InputList[0]);
foreach (string EachStr in InputList.Skip(1)) {
SplitAct(EachStr);
long FromNode = wkArr[0];
long ToNode = wkArr[1];
long Cost = wkArr[2];
if (mToNodeListDict.ContainsKey(FromNode) == false) {
mToNodeListDict[FromNode] = new List<NodeInfoDef>();
}
NodeInfoDef WillAdd1;
WillAdd1.ToNode = ToNode;
WillAdd1.Cost = Cost;
mToNodeListDict[FromNode].Add(WillAdd1);
if (mToNodeListDict.ContainsKey(ToNode) == false) {
mToNodeListDict[ToNode] = new List<NodeInfoDef>();
}
NodeInfoDef WillAdd2;
WillAdd2.ToNode = FromNode;
WillAdd2.Cost = Cost;
mToNodeListDict[ToNode].Add(WillAdd2);
}
// 色[頂点番号]なDict
var AnswerDict = new Dictionary<long, long>();
JyoutaiDef WillPush;
WillPush.CurrNode = 1;
WillPush.CostSum = 0;
var Stk = new Stack<JyoutaiDef>();
Stk.Push(WillPush);
var VisitedSet = new HashSet<long>();
while (Stk.Count > 0) {
JyoutaiDef Popeed = Stk.Pop();
AnswerDict[Popeed.CurrNode] = Popeed.CostSum % 2;
foreach (NodeInfoDef EachToNode in mToNodeListDict[Popeed.CurrNode]) {
if (VisitedSet.Add(EachToNode.ToNode) == false) {
continue;
}
WillPush.CurrNode = EachToNode.ToNode;
WillPush.CostSum = Popeed.CostSum + EachToNode.Cost;
Stk.Push(WillPush);
}
}
foreach (var EachPair in AnswerDict.OrderBy(pX => pX.Key)) {
Console.WriteLine(EachPair.Value);
}
}
}
解説
木なので、任意のノードから深さ優先探索を行い、
Cost合計が偶数なら0
Cost合計が奇数なら1
を割り振ってます。