ALDS1_11_C: Breadth First Search

問題へのリンク

C#のソース

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

// Q038 幅優先探索 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=jp
class Program
{
    static string InputPattern = "InputX";

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

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

    static int mN;

    // 隣接リスト
    static Dictionary<int, int[]> mToNodeArrDict = new Dictionary<int, int[]>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        mN = int.Parse(InputList[0]);

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

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            int NodeID = wkArr[0];
            int[] ToNodeArr = EachStr.Split(' ').Skip(2).Select(pX => int.Parse(pX)).ToArray();

            mToNodeArrDict[NodeID] = ToNodeArr;
        }

        ExecBFS(1); // 頂点1から幅優先探索
    }

    struct JyoutaiDef
    {
        internal int CurrNode;
        internal int Distance;
    }

    // 幅優先探索を行う
    static void ExecBFS(int pStartNode)
    {
        // ノードごとの距離のDict
        var DistanceDict = new Dictionary<int, int>();

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrNode = pStartNode;
        WillEnqueue.Distance = 0;
        Que.Enqueue(WillEnqueue);
        DistanceDict[1] = WillEnqueue.Distance;

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();

            foreach (int EachToNode in mToNodeArrDict[Dequeued.CurrNode]) {
                if (DistanceDict.ContainsKey(EachToNode)) continue;

                WillEnqueue.CurrNode = EachToNode;
                WillEnqueue.Distance = Dequeued.Distance + 1;
                Que.Enqueue(WillEnqueue);
                DistanceDict[EachToNode] = WillEnqueue.Distance;
            }
        }

        // ノードごとの最短距離を出力
        for (int I = 1; I <= mN; I++) {
            if (DistanceDict.ContainsKey(I) == false) {
                Console.WriteLine("{0} -1", I);
            }
            else {
                Console.WriteLine("{0} {1}", I, DistanceDict[I]);
            }
        }
    }
}

解説

Queueクラスで幅優先探索してます。