ABC266-F Well-defined Path Queries on a Namori

問題へのリンク

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("5");
            WillReturn.Add("1 2");
            WillReturn.Add("2 3");
            WillReturn.Add("1 3");
            WillReturn.Add("1 4");
            WillReturn.Add("2 5");
            WillReturn.Add("3");
            WillReturn.Add("1 2");
            WillReturn.Add("1 4");
            WillReturn.Add("1 5");
            //No
            //Yes
            //No
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            WillReturn.Add("3 5");
            WillReturn.Add("5 7");
            WillReturn.Add("4 8");
            WillReturn.Add("2 9");
            WillReturn.Add("1 2");
            WillReturn.Add("7 9");
            WillReturn.Add("1 6");
            WillReturn.Add("4 10");
            WillReturn.Add("2 5");
            WillReturn.Add("2 10");
            WillReturn.Add("10");
            WillReturn.Add("1 8");
            WillReturn.Add("6 9");
            WillReturn.Add("8 10");
            WillReturn.Add("6 8");
            WillReturn.Add("3 10");
            WillReturn.Add("3 9");
            WillReturn.Add("1 10");
            WillReturn.Add("5 8");
            WillReturn.Add("1 10");
            WillReturn.Add("7 8");
            //Yes
            //No
            //Yes
            //Yes
            //No
            //No
            //Yes
            //No
            //Yes
            //No
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mN;
    static List<int>[] mEdgeListArr; // 隣接グラフ

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray();

        mN = int.Parse(InputList[0]);
        mEdgeListArr = new List<int>[mN + 1];

        for (int I = 1; I <= mN; I++) {
            mEdgeListArr[I] = new List<int>();
        }

        foreach (string EachStr in InputList.Skip(1).Take(mN)) {
            SplitAct(EachStr);
            int FromNode = wkArr[0];
            int ToNode = wkArr[1];

            mEdgeListArr[FromNode].Add(ToNode);
            mEdgeListArr[ToNode].Add(FromNode);
        }

        var InsDeriveBridge = new DeriveBridge(1, mN, mEdgeListArr);
        var Query = InsDeriveBridge.DeriveBridgeEnum();

        // 橋の辺のHashSet
        var EdgeSet = new HashSet<long>();
        foreach (DeriveBridge.BridgeInfoDef EachBridge in Query) {
            int FromNode = EachBridge.FromNode;
            int ToNode = EachBridge.ToNode;
            EdgeSet.Add(GetHash(FromNode, ToNode));
        }

        // 枝を全探索して、橋の両端でなければ、サイクルノードである
        var CycleNodeSet = new HashSet<int>();
        for (int I = 1; I <= mEdgeListArr.GetUpperBound(0); I++) {
            foreach (int EachToNode in mEdgeListArr[I]) {
                int FromNode = I;
                int ToNode = EachToNode;
                long CurrHash = GetHash(FromNode, ToNode);
                if (EdgeSet.Contains(CurrHash)) continue;

                CycleNodeSet.Add(FromNode);
                CycleNodeSet.Add(ToNode);
            }
        }

        // 木のID[ノードID]なDict
        var TreeDict = new Dictionary<int, int>();

        foreach (int EachCycleNode in CycleNodeSet) {
            var Stk = new Stack<JyoutaiDef>();
            JyoutaiDef WillPush;
            WillPush.CurrNode = EachCycleNode;
            Stk.Push(WillPush);
            TreeDict[EachCycleNode] = EachCycleNode;

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

                foreach (int EachToNode in mEdgeListArr[Popped.CurrNode]) {
                    if (CycleNodeSet.Contains(EachToNode)) continue;
                    if (TreeDict.ContainsKey(EachToNode)) continue;

                    WillPush.CurrNode = EachToNode;
                    Stk.Push(WillPush);
                    TreeDict[EachToNode] = EachCycleNode;
                }
            }
        }

        // クエリに回答する
        var sb = new System.Text.StringBuilder();
        foreach (string EachStr in InputList.Skip(1 + mN + 1)) {
            SplitAct(EachStr);
            int X = wkArr[0];
            int Y = wkArr[1];

            if (CycleNodeSet.Contains(X) && CycleNodeSet.Contains(Y)) {
                sb.AppendLine("No");
                continue;
            }

            if (TreeDict[X] == TreeDict[Y]) {
                sb.AppendLine("Yes");
            }
            else {
                sb.AppendLine("No");
            }
        }
        Console.Write(sb.ToString());
    }

    struct JyoutaiDef
    {
        internal int CurrNode;
    }

    // 無向辺のハッシュ値を返す
    static long GetHash(int pFrom, int pTo)
    {
        long MinNode = Math.Min(pFrom, pTo);
        long MaxNode = Math.Max(pFrom, pTo);
        return MinNode * 100000000 + MaxNode;
    }
}

#region DeriveBridge
// 無向グラフの橋の列挙を返す
internal class DeriveBridge
{
    private int mMinNode;
    private int mMaxNode;
    private int mTimer;

    private List<int>[] mEdgeListArr; // 隣接グラフ
    private bool[] mVisitedArr; // 訪問済ノードの管理
    private int[] mPreNumArr; // DFSツリーでの訪問順
    private int[] mParentArr; // 親ノード
    private int[] mLowestArr; // LowLink

    // コンストラクタ
    internal DeriveBridge(int pMinNode, int pMaxNode, List<int>[] pEdgeListArr)
    {
        mMinNode = pMinNode;
        mMaxNode = pMaxNode;
        mEdgeListArr = pEdgeListArr;

        mVisitedArr = new bool[mMaxNode + 1];
        mPreNumArr = new int[mMaxNode + 1];
        mParentArr = new int[mMaxNode + 1];
        mLowestArr = new int[mMaxNode + 1];
    }

    internal struct BridgeInfoDef
    {
        internal int FromNode;
        internal int ToNode;
    }

    // 橋の列挙を返す
    internal IEnumerable<BridgeInfoDef> DeriveBridgeEnum()
    {
        mTimer = 1;
        // Lowestの計算
        DFS(mMinNode, -1);

        var BridgeHashSet = new HashSet<long>();
        var BridgeInfoList = new List<BridgeInfoDef>();

        // 以下の条件を満たす辺 (From,To) が橋(bridge)
        // PewNum[From] < LowLink[To]
        for (int I = mMinNode; I <= mMaxNode; I++) {
            foreach (int EachNext in mEdgeListArr[I]) {
                if (mPreNumArr[I] < mLowestArr[EachNext]) {
                    int FromNode = Math.Min(I, EachNext);
                    int ToNode = Math.Max(I, EachNext);
                    long Hash = GetHash(FromNode, ToNode);
                    if (BridgeHashSet.Add(Hash)) {
                        BridgeInfoDef WillAdd;
                        WillAdd.FromNode = FromNode;
                        WillAdd.ToNode = ToNode;
                        BridgeInfoList.Add(WillAdd);
                    }
                }
            }
        }
        var Query = BridgeInfoList.OrderBy(pX => pX.FromNode).ThenBy(pX => pX.ToNode);
        foreach (var EachBridgeInfo in Query) {
            yield return EachBridgeInfo;
        }
    }

    // 深さ優先探索を行い、DFSツリーを構築する
    private void DFS(int pCurr, int pPrev)
    {
        mPreNumArr[pCurr] = mLowestArr[pCurr] = mTimer;
        mTimer++;

        mVisitedArr[pCurr] = true;

        foreach (int EachNext in mEdgeListArr[pCurr]) {
            if (mVisitedArr[EachNext] == false) {
                // ノードCurrからノードNextを訪問する直前の処理
                mParentArr[EachNext] = pCurr;

                DFS(EachNext, pCurr);

                // ノードNextの探索が完了した直後の処理
                mLowestArr[pCurr] = Math.Min(mLowestArr[pCurr], mLowestArr[EachNext]);
            }
            else if (EachNext != pPrev) {
                // エッジ Curr --> EachNext が 後退辺の場合の処理
                mLowestArr[pCurr] = Math.Min(mLowestArr[pCurr], mPreNumArr[EachNext]);
            }
        }
        // ノードCurrの探索が終了した直後の処理
    }

    // 無向辺のハッシュ値を返す
    private static long GetHash(int pFrom, int pTo)
    {
        long MinNode = Math.Min(pFrom, pTo);
        long MaxNode = Math.Max(pFrom, pTo);
        return MinNode * 100000000 + MaxNode;
    }
}
#endregion

解説

最初に無向グラフの枝の中で、橋を列挙します。
すると、橋でない枝の両端ノードを、サイクルに含まれるノードとして、
サイクルに含まれるノードのsetを作ることができます。

後は、サイクルのノードごとに
子ノードをDFSで列挙しておけば、
クエリにO(1)で答えることができます。