ABC232-C Graph Isomorphism

問題へのリンク

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

    static int mN;
    static int mM;

    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]);
        mN = wkArr[0];
        mM = wkArr[1];
        int UB = mN - 1;

        int[,] HasEdgeArr1 = new int[UB + 1, UB + 1];
        int[,] HasEdgeArr2 = new int[UB + 1, UB + 1];

        foreach (string EachStr in InputList.Skip(1).Take(mM)) {
            SplitAct(EachStr);
            HasEdgeArr1[wkArr[0] - 1, wkArr[1] - 1] = 1;
            HasEdgeArr1[wkArr[1] - 1, wkArr[0] - 1] = 1;
        }

        foreach (string EachStr in InputList.Skip(1 + mM)) {
            SplitAct(EachStr);
            HasEdgeArr2[wkArr[0] - 1, wkArr[1] - 1] = 1;
            HasEdgeArr2[wkArr[1] - 1, wkArr[0] - 1] = 1;
        }

        IEnumerable<int[]> EnumPermutation =
            CppPermutationClass<int>.DerivePermutation(Enumerable.Range(0, mN));

        string Hash1 = DeriveHash(HasEdgeArr1);

        foreach (int[] EachDFSResult in EnumPermutation) {
            string Hash2 = DeriveHash2(HasEdgeArr2, EachDFSResult);
            if (Hash1 == Hash2) {
                Console.WriteLine("Yes");
                return;
            }
        }
        Console.WriteLine("No");
    }

    // 隣接行列ののハッシュ値を求める
    static string DeriveHash(int[,] pArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int I = 0; I <= pArr.GetUpperBound(0); I++) {
            for (int J = 0; J <= pArr.GetUpperBound(1); J++) {
                sb.Append(pArr[I, J]);
            }
        }
        return sb.ToString();
    }

    // 隣接行列のハッシュ値を求める
    static string DeriveHash2(int[,] pArr, int[] pChangeArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int I = 0; I <= pArr.GetUpperBound(0); I++) {
            int IndI = Array.IndexOf(pChangeArr, I);
            for (int J = 0; J <= pArr.GetUpperBound(1); J++) {
                int IndJ = Array.IndexOf(pChangeArr, J);
                sb.Append(pArr[IndI, IndJ]);
            }
        }
        return sb.ToString();
    }
}

#region CppPermutationClass
internal static class CppPermutationClass<Type> where Type : IComparable
{
    // C++のNextPermutationの結果の列挙を返す
    internal static IEnumerable<Type[]> DerivePermutation(IEnumerable<Type> pEnum)
    {
        Type[] wkArr = pEnum.ToArray();
        do {
            yield return wkArr;
        } while (NextPermutation(ref wkArr));
    }

    // C++のNextPermutationを模倣
    internal static bool NextPermutation(ref Type[] pArr)
    {
        // 右から左に見ていき、初めて小さくなった要素を求める
        int WillChangeInd = -1;
        for (int I = pArr.GetUpperBound(0) - 1; I >= 0; I--) {
            if (pArr[I].CompareTo(pArr[I + 1]) == -1) {
                WillChangeInd = I;
                break;
            }
        }

        if (WillChangeInd == -1) {
            return false;
        }

        // 初めて小さくなった要素より右の変更すべき要素を求める
        int MinValInd = WillChangeInd + 1;
        for (int I = WillChangeInd + 2; I <= pArr.GetUpperBound(0); I++) {
            if (pArr[WillChangeInd].CompareTo(pArr[I]) == 1) continue;

            if (pArr[MinValInd].CompareTo(pArr[I]) == 1) {
                MinValInd = I;
            }
        }

        // 変更すべき要素と3角交換
        Type wkStr = pArr[WillChangeInd];
        pArr[WillChangeInd] = pArr[MinValInd];
        pArr[MinValInd] = wkStr;

        // 正順で連結
        var ResultList = new List<Type>();
        for (int I = 0; I <= WillChangeInd; I++) {
            ResultList.Add(pArr[I]);
        }
        // 逆順で連結
        for (int I = pArr.GetUpperBound(0); I >= WillChangeInd + 1; I--) {
            ResultList.Add(pArr[I]);
        }

        pArr = ResultList.ToArray();
        return true;
    }

    // C++のPrevPermutationを模倣
    internal static bool PrevPermutation(ref Type[] pArr)
    {
        // 右から左に見ていき、初めて大きくなった要素を求める
        int WillChangeInd = -1;
        for (int I = pArr.GetUpperBound(0) - 1; I >= 0; I--) {
            if (pArr[I].CompareTo(pArr[I + 1]) == 1) {
                WillChangeInd = I;
                break;
            }
        }

        if (WillChangeInd == -1) {
            return false;
        }

        // 初めて大きくなった要素より右の変更すべき要素を求める
        int MinValInd = WillChangeInd + 1;
        for (int I = WillChangeInd + 2; I <= pArr.GetUpperBound(0); I++) {
            if (pArr[WillChangeInd].CompareTo(pArr[I]) == -1) continue;

            if (pArr[MinValInd].CompareTo(pArr[I]) == -1) {
                MinValInd = I;
            }
        }

        // 変更すべき要素と3角交換
        Type wkStr = pArr[WillChangeInd];
        pArr[WillChangeInd] = pArr[MinValInd];
        pArr[MinValInd] = wkStr;

        // 正順で連結
        var ResultList = new List<Type>();
        for (int I = 0; I <= WillChangeInd; I++) {
            ResultList.Add(pArr[I]);
        }
        // 逆順で連結
        for (int I = pArr.GetUpperBound(0); I >= WillChangeInd + 1; I--) {
            ResultList.Add(pArr[I]);
        }

        pArr = ResultList.ToArray();
        return true;
    }
}
#endregion

解説

隣接行列の添字入替をして、一致するかを判定してます。