AtCoderのABC
次のABCの問題へ
前のABCの問題へ
ABC226-E Just one
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 3");
WillReturn.Add("1 2");
WillReturn.Add("1 3");
WillReturn.Add("2 3");
//2
}
else if (InputPattern == "Input2") {
WillReturn.Add("2 1");
WillReturn.Add("1 2");
//0
}
else if (InputPattern == "Input3") {
WillReturn.Add("7 7");
WillReturn.Add("1 2");
WillReturn.Add("2 3");
WillReturn.Add("3 4");
WillReturn.Add("4 2");
WillReturn.Add("5 6");
WillReturn.Add("6 7");
WillReturn.Add("7 5");
//4
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
const long Hou = 998244353;
static int mN;
// 隣接リスト
static Dictionary<int, List<int>> mToNodeListDict = new Dictionary<int, List<int>>();
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]);
mN = wkArr[0];
foreach (string EachStr in InputList.Skip(1)) {
SplitAct(EachStr);
int FromNode = wkArr[0];
int ToNode = wkArr[1];
if (mToNodeListDict.ContainsKey(FromNode) == false) {
mToNodeListDict[FromNode] = new List<int>();
}
if (mToNodeListDict.ContainsKey(ToNode) == false) {
mToNodeListDict[ToNode] = new List<int>();
}
mToNodeListDict[FromNode].Add(ToNode);
mToNodeListDict[ToNode].Add(FromNode);
}
// 連結成分分解を行う
Dictionary<int, List<int>> SCCListDict = DeriveSCCListDict();
long Answer = 1;
foreach (var EachPair in SCCListDict) {
long NodeCnt = EachPair.Value.Count;
long EdgeCnt = 0;
foreach (int EachNode in EachPair.Value) {
if (mToNodeListDict.ContainsKey(EachNode)) {
EdgeCnt += mToNodeListDict[EachNode].Count;
}
}
if (NodeCnt == EdgeCnt / 2) {
Answer *= 2;
Answer %= Hou;
}
else {
Answer = 0;
break;
}
}
Console.WriteLine(Answer);
}
struct JyoutaiDef1
{
internal int CurrNode; // 現在ノード
}
// 連結成分分解を行う
static Dictionary<int, List<int>> DeriveSCCListDict()
{
var SCCListDict = new Dictionary<int, List<int>>();
var VisitedSet = new HashSet<int>();
for (int I = 1; I <= mN; I++) {
if (VisitedSet.Contains(I)) continue;
SCCListDict[I] = new List<int>();
SCCListDict[I].Add(I);
var Stk = new Stack<JyoutaiDef1>();
JyoutaiDef1 WillPush;
WillPush.CurrNode = I;
Stk.Push(WillPush);
VisitedSet.Add(I);
while (Stk.Count > 0) {
JyoutaiDef1 Popped = Stk.Pop();
// 子ノード無しの場合
if (mToNodeListDict.ContainsKey(Popped.CurrNode) == false)
continue;
foreach (int EachToNode in mToNodeListDict[Popped.CurrNode]) {
if (VisitedSet.Add(EachToNode) == false) continue;
SCCListDict[I].Add(EachToNode);
WillPush.CurrNode = EachToNode;
Stk.Push(WillPush);
}
}
}
return SCCListDict;
}
}
解説
連結成分ごとに独立して考えます。
有向辺は、必ず1つのノードから出るので、
必要条件として、
辺の数 = ノードがあります。
木の性質、 辺の数 = ノード数 - 1
を考えると、木にサイクルが1つできた形になって、
サイクルのノードの向きが2通りになるので
連結成分ごとに積の法則を使えば、解が分かります。