GRL_3_A: Articulation Points

問題へのリンク

C#のソース

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

// Q049 関節点 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_A&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
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 4");
            WillReturn.Add("0 1");
            WillReturn.Add("1 2");
            WillReturn.Add("2 3");
            WillReturn.Add("3 4");
            //1
            //2
            //3
        }
        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);
        }
        art_points();
    }

    // 関節点を求める
    static void art_points()
    {
        mTimer = 1;
        // Lowestの計算
        DFS(0, -1);  // 0 == root

        var ArtPointsSet = new HashSet<int>();
        int ParentCnt = 0;
        for (int I = 1; I <= UB; I++) {
            int ParentNode = mParentArr[I];
            if (ParentNode == 0) {
                ParentCnt++;
            }
            else if (mPreNumArr[ParentNode] <= mLowestArr[I]) {
                ArtPointsSet.Add(ParentNode);
            }
        }
        if (ParentCnt > 1) ArtPointsSet.Add(0);

        foreach (int EachInt in ArtPointsSet.OrderBy(pX => pX)) {
            Console.WriteLine(EachInt);
        }
    }

    // 深さ優先探索を行い、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を使って解いてます。