ABC068-C Cat Snuke and a Voyage

■■■問題■■■

高橋キングダムには、高橋諸島という、N個の島からなる諸島があります。
便宜上、これらの島を島1、島2、 ・・・ 、島Nと呼ぶことにします。

これらの諸島の間では、船の定期便がM種類運行されています。
定期便はそれぞれ2つの島の間を行き来しており、i種類目の定期便を使うと、
島aiと島biの間を行き来する事ができます。

すぬけくんは今島1にいて、島Nに行きたいと思っています。
しかし、島1から島Nへの定期便は存在しないことがわかりました。
なので、定期便を2つ使うことで、島Nに行けるか調べたいと思っています。

これを代わりに調べてあげてください。

■■■入力■■■

N M
a1 b1
a2 b2
・
・
・
aM bM

●3 <= N <= 20万
●1 <= M <= 20万
●1 <= ai < bi <= N
●(ai,bi) != (1,N)
●i != j ならば (ai,bi) != (aj,bj)

■■■出力■■■

定期便を2つ使いたどり着けるならばPOSSIBLE、たどり着けないならばIMPOSSIBLEと出力する。

C#のソース

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

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("3 2");
            WillReturn.Add("1 2");
            WillReturn.Add("2 3");
            //POSSIBLE
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 3");
            WillReturn.Add("1 2");
            WillReturn.Add("2 3");
            WillReturn.Add("3 4");
            //IMPOSSIBLE
            //島4へ行くには、定期便を3つ使う必要があります。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("100000 1");
            WillReturn.Add("1 99999");
            //IMPOSSIBLE
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("5 5");
            WillReturn.Add("1 3");
            WillReturn.Add("4 5");
            WillReturn.Add("2 3");
            WillReturn.Add("2 4");
            WillReturn.Add("1 4");
            //POSSIBLE
            //島1、島4、島5と移動すれば2つの定期便で移動可能です。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    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]);
        int N = wkArr[0];

        var ZenhanSet = new HashSet<int>();
        var KouhanSet = new HashSet<int>();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            int A = wkArr[0];
            int B = wkArr[1];

            if (A == 1) {
                ZenhanSet.Add(B);
            }
            if (B == N) {
                KouhanSet.Add(A);
            }
        }
        ZenhanSet.IntersectWith(KouhanSet);

        if (ZenhanSet.Count > 0) {
            Console.WriteLine("POSSIBLE");
        }
        else Console.WriteLine("IMPOSSIBLE");
    }
}

解説

双方向探索チックに解いてます。