#1187516 (C#(csc)) No.3695 同室と別室

• 問題: No.3695 同室と別室
• ユーザー: aketijyuuzou
• 提出日時: 2026-09-18 21:38:40
• 言語: C#(csc) (csc 3.9.0)
• 結果: AC
• 実行時間: 411 ms / 2,000 ms
• コード長: 9,098 bytes
• コンパイル時間: 2,542 ms
• コンパイル使用メモリ: 112,512 KB
• 実行使用メモリ: 92,676 KB
• 最終ジャッジ日時: 2026-09-18 21:38:49
• 合計ジャッジ時間: 3,773 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 2
other	AC * 13

コンパイルメッセージ

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/3695
// yukicoder 3695 同室と別室
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("4 2");
            WillReturn.Add("0 1 2");
            WillReturn.Add("1 3 4");
            //4
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 3");
            WillReturn.Add("0 1 2");
            WillReturn.Add("1 2 3");
            WillReturn.Add("0 1 3");
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    const long Hou = 998244353;

    class QueryInfoDef
    {
        internal long T;
        internal long A;
        internal long B;
    }
    static List<QueryInfoDef> mQueryInfoList = new List<QueryInfoDef>();

    // 隣接リスト
    static Dictionary<long, List<long>> mToNodeListDict = new Dictionary<long, List<long>>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        long N = wkArr[0];

        var InsUnionFind = new UnionFind();
        for (long I = 1; I <= N; I++) {
            InsUnionFind.MakeSet(I);
        }

        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            var WillAdd = new QueryInfoDef();
            WillAdd.T = wkArr[0];
            WillAdd.A = wkArr[1];
            WillAdd.B = wkArr[2];
            mQueryInfoList.Add(WillAdd);
        }

        // 処理01 クエリ0でUnionFind
        foreach (QueryInfoDef EachQueryInfo in mQueryInfoList.FindAll(pX => pX.T == 0)) {
            InsUnionFind.Unite(EachQueryInfo.A, EachQueryInfo.B);
        }

        // 処理02 クエリ1で既に同じ木なら不可
        foreach (QueryInfoDef EachQueryInfo in mQueryInfoList.FindAll(pX => pX.T == 1)) {
            long RootNode1 = InsUnionFind.FindSet(EachQueryInfo.A);
            long RootNode2 = InsUnionFind.FindSet(EachQueryInfo.B);
            if (RootNode1 == RootNode2) {
                Console.WriteLine(0);
                return;
            }
        }

        // 処理03 各ノードをUnionFindのルートノードでまとめる
        for (int I = 0; I <= mQueryInfoList.Count - 1; I++) {
            long NewA = mQueryInfoList[I].A;
            long NewB = mQueryInfoList[I].B;
            NewA = InsUnionFind.FindSet(NewA);
            NewB = InsUnionFind.FindSet(NewB);

            mQueryInfoList[I].A = NewA;
            mQueryInfoList[I].B = NewB;
        }

        // 存在するノードの管理
        var NodeSet = new HashSet<long>();
        for (long I = 1; I <= N; I++) {
            if (I == InsUnionFind.FindSet(I)) {
                NodeSet.Add(I);
            }
        }

        // 処理04 無向グラフの連結成分分解を行う
        foreach (QueryInfoDef EachQueryInfo in mQueryInfoList.FindAll(pX => pX.T == 1)) {
            long FromNode = EachQueryInfo.A;
            long ToNode = EachQueryInfo.B;

            if (mToNodeListDict.ContainsKey(FromNode) == false) {
                mToNodeListDict[FromNode] = new List<long>();
            }
            if (mToNodeListDict.ContainsKey(ToNode) == false) {
                mToNodeListDict[ToNode] = new List<long>();
            }
            mToNodeListDict[FromNode].Add(ToNode);
            mToNodeListDict[ToNode].Add(FromNode);
        }
        ExecDFS(NodeSet);

        // 処理05 連結成分ごとに二部グラフにできるかを判定
        foreach (long EachStaNode in mTreeDict.Values.Distinct()) {
            if (ExecDFS(EachStaNode) == false) {
                Console.WriteLine(0);
                return;
            }
        }

        // 二部グラフにできるなら、連結成分ごとに2通りの彩色があるので
        // 解は、2のべき乗で求まる。
        // 成約も緩いので繰り返り二乗法は不要である
        long Answer = 1;
        foreach (long EachStaNode in mTreeDict.Values.Distinct()) {
            Answer *= 2;
            Answer %= Hou;
        }
        Console.WriteLine(Answer);
    }

    // 無向グラフの連結成分分解
    // 代表ノード[ノード]なDict
    static Dictionary<long, long> mTreeDict = new Dictionary<long, long>();
    struct JyoutaiDef1
    {
        internal long CurrNode;
    }
    // 深さ優先探索を行う
    static void ExecDFS(HashSet<long> pNodeSet)
    {
        foreach (long I in pNodeSet) {
            if (mTreeDict.ContainsKey(I)) continue;

            var Stk = new Stack<JyoutaiDef1>();
            JyoutaiDef1 WillPush;
            WillPush.CurrNode = I;
            Stk.Push(WillPush);
            mTreeDict[I] = I;

            while (Stk.Count > 0) {
                JyoutaiDef1 Popped = Stk.Pop();

                // 子ノード無しの場合
                if (mToNodeListDict.ContainsKey(Popped.CurrNode) == false)
                    continue;

                foreach (int EachToNode in mToNodeListDict[Popped.CurrNode]) {
                    if (mTreeDict.ContainsKey(EachToNode)) continue;

                    WillPush.CurrNode = EachToNode;
                    Stk.Push(WillPush);
                    mTreeDict[EachToNode] = I;
                }
            }
        }
    }

    // 二部グラフの判定
    static Dictionary<long, long> mLevelMod2Dict = new Dictionary<long, long>();
    struct JyoutaiDef2
    {
        internal long CurrNode;
        internal long Level;
    }
    static bool ExecDFS(long pStaNode)
    {
        mLevelMod2Dict.Clear();

        var Stk = new Stack<JyoutaiDef2>();
        JyoutaiDef2 WillPush;
        WillPush.CurrNode = pStaNode;
        WillPush.Level = 1;
        Stk.Push(WillPush);

        while (Stk.Count > 0) {
            JyoutaiDef2 Popped = Stk.Pop();

            // 訪問済なら矛盾がないかのチェックだけ行う
            if (mLevelMod2Dict.ContainsKey(Popped.CurrNode)) {
                long CorrectLevelMod2 = mLevelMod2Dict[Popped.CurrNode];
                if (CorrectLevelMod2 != Popped.Level % 2) {
                    return false;
                }
                continue;
            }

            // 未訪問なら採色
            mLevelMod2Dict[Popped.CurrNode] = Popped.Level % 2;

            if (mToNodeListDict.ContainsKey(Popped.CurrNode) == false) {
                continue;
            }
            foreach (long EachToNode in mToNodeListDict[Popped.CurrNode]) {
                WillPush.CurrNode = EachToNode;
                WillPush.Level = Popped.Level + 1;
                Stk.Push(WillPush);
            }
        }
        return true;
    }

}

#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