ABC260-F Find 4-cycle

問題へのリンク

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

    static int mS;
    static int mT;

    // 隣接リスト
    static Dictionary<int, List<int>> mToNodeListDict = new Dictionary<int, List<int>>();

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

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

        SplitAct(InputList[0]);
        mS = wkArr[0];
        mT = wkArr[1];

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

            if (mToNodeListDict.ContainsKey(FromNode) == false) {
                mToNodeListDict[FromNode] = new List<int>();
            }
            if (mToNodeListDict.ContainsKey(ToNode) == false) {
                mToNodeListDict[ToNode] = new List<int>();
            }
            mToNodeListDict[FromNode].Add(ToNode);
            mToNodeListDict[ToNode].Add(FromNode);
        }

        int AnswerT1;
        int AnswerT2;
        bool Result1 = Solve1(out AnswerT1, out AnswerT2);

        if (Result1 == false) {
            Console.WriteLine(-1);
            return;
        }
        Solve2(AnswerT1, AnswerT2);
    }

    static bool Solve1(out int pAnswerT1, out int pAnswerT2)
    {
        pAnswerT1 = 0;
        pAnswerT2 = 0;

        // SのCnt[Tのペアのハッシュ値]
        var CntDict = new Dictionary<long, int>();
        for (int I = 1; I <= mS; I++) {

            // 連結ノードで2重ループ
            if (mToNodeListDict.ContainsKey(I) == false) continue;
            List<int> ConnNodeList = mToNodeListDict[I];

            for (int J = 0; J <= ConnNodeList.Count - 1; J++) {
                for (int K = J + 1; K <= ConnNodeList.Count - 1; K++) {
                    long Hash = GetHash(ConnNodeList[J], ConnNodeList[K]);

                    if (CntDict.ContainsKey(Hash) == false) {
                        CntDict[Hash] = 0;
                    }
                    CntDict[Hash]++;

                    if (CntDict[Hash] == 2) {
                        pAnswerT1 = ConnNodeList[J];
                        pAnswerT2 = ConnNodeList[K];
                        return true;
                    }
                }
            }
        }
        return false;
    }

    static void Solve2(int pAnswerT1, int pAnswerT2)
    {
        // SのList[Tのペアのハッシュ値]
        var SListDict = new Dictionary<long, List<int>>();
        for (int I = 1; I <= mS; I++) {

            // 連結ノードで2重ループ
            if (mToNodeListDict.ContainsKey(I) == false) continue;
            List<int> ConnNodeList = mToNodeListDict[I];

            for (int J = 0; J <= ConnNodeList.Count - 1; J++) {
                if (ConnNodeList[J] != pAnswerT1 && ConnNodeList[J] != pAnswerT2) {
                    continue;
                }
                for (int K = J + 1; K <= ConnNodeList.Count - 1; K++) {
                    if (ConnNodeList[K] != pAnswerT1 && ConnNodeList[K] != pAnswerT2) {
                        continue;
                    }

                    long Hash = GetHash(ConnNodeList[J], ConnNodeList[K]);

                    if (SListDict.ContainsKey(Hash) == false) {
                        SListDict[Hash] = new List<int>();
                    }
                    SListDict[Hash].Add(I);

                    if (SListDict[Hash].Count == 2) {
                        Console.WriteLine("{0} {1} {2} {3}",
                            ConnNodeList[J], ConnNodeList[K],
                            SListDict[Hash][0], SListDict[Hash][1]);
                        return;
                    }
                }
            }
        }
        return;
    }

    // Tのノード2つからなるハッシュ値を求める
    static long GetHash(int p1, int p2)
    {
        long MinNode = Math.Min(p1, p2);
        long MaxNode = Math.Max(p1, p2);
        return MinNode * 1000000 + MaxNode;
    }
}

解説

2部グラフで
Tが3000しかないので
3000 C 2 = 1500*2999で
鳩の巣原理を使うことができます。