GRL_3_B: Bridges

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

// Q053 橋 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B&lang=jp
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();
        if (InputPattern == "Input1") {
            WillReturn.Add("4 4");
            WillReturn.Add("0 1");
            WillReturn.Add("0 2");
            WillReturn.Add("1 2");
            WillReturn.Add("2 3");
            //2 3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 4");
            WillReturn.Add("0 1");
            WillReturn.Add("1 2");
            WillReturn.Add("2 3");
            WillReturn.Add("3 4");
            //0 1
            //1 2
            //2 3
            //3 4
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mV;
    static int UB;

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

    static int mTimer;

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

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

        SplitAct(InputList[0]);
        mV = wkArr[0];

        UB = mV - 1;

        mEdgeListArr = new List<int>[UB + 1];
        mVisitedArr = new bool[UB + 1];
        mPreNumArr = new int[UB + 1];
        mParentArr = new int[UB + 1];
        mLowestArr = new int[UB + 1];

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

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            int s = wkArr[0];
            int e = wkArr[1];
            mEdgeListArr[s].Add(e);
            mEdgeListArr[e].Add(s);
        }
        DeriveBridge();
    }

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

    // 橋を出力する
    static void DeriveBridge()
    {
        mTimer = 1;
        // Lowestの計算
        DFS(0, -1);  // 0 == root

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

        // 以下の条件を満たす辺 (From,To) が橋(bridge)
        // PewNum[From] < LowLink[To]
        for (int I = 0; I <= UB; I++) {
            foreach (int EachNext in mEdgeListArr[I]) {
                if (mPreNumArr[I] < mLowestArr[EachNext]) {
                    int FromNode = Math.Min(I, EachNext);
                    int ToNode = Math.Max(I, EachNext);
                    string Hash = string.Format("{0} {1}", 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) {
            Console.WriteLine("{0} {1}", EachBridgeInfo.FromNode, EachBridgeInfo.ToNode);
        }
    }

    // 深さ優先探索を行い、DFSツリーを構築する
    static 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の探索が終了した直後の処理
    }
}

解説

lowlinkを使って解いてます。