Q19 友達の友達は友達？

C#のソース

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

class Program
{
    const int LimitN = 60;
    const int LimitLevel = 6;

    static void Main()
    {
        CreateFriendArrDict();

        var AnswerKouhoList = new List<int[]>();
        for (int LoopStaNum = 2; LoopStaNum <= LimitN; LoopStaNum++) {
            //素数なら除外
            if (IsPrime(LoopStaNum)) continue;
            
            AnswerKouhoList.AddRange(ExecDFS(LoopStaNum));
        }
        int AnswerN = AnswerKouhoList.Min(X => X.Max());
        AnswerKouhoList.RemoveAll(A => Array.Exists(A, B => B > AnswerN));

        Console.WriteLine("最小のN={0}", AnswerN);
        foreach (int[] EachArr in AnswerKouhoList) {
            Array.ForEach(EachArr, X => Console.Write("{0},", X));
            Console.WriteLine();
        }
    }

    //友達の配列のDictを作成
    static Dictionary<int, List<int>> FriendArrDict = new Dictionary<int, List<int>>();
    static void CreateFriendArrDict()
    {
        for (int I = 2; I <= LimitN; I++) {
            FriendArrDict[I] = new List<int>();
        }

        for (int I = 2; I <= LimitN; I++) {
            for (int J = 2; J <= LimitN; J++) {
                if (I == J) continue;

                if (DeriveGCD(I, J) > 1)
                    FriendArrDict[J].Add(I);
            }
        }

        //素数ならRemove
        foreach (int EachKey in FriendArrDict.Keys.ToArray()) {
            if (IsPrime(EachKey)) FriendArrDict.Remove(EachKey);
            else FriendArrDict[EachKey].RemoveAll(X => IsPrime(X));
        }
    }

    //ユークリッドの互除法で2数の最大公約数を求める
    static int DeriveGCD(int pVal1, int pVal2)
    {
        int WarareruKazu = pVal2;
        int WaruKazu = pVal1;

        while (true) {
            int Amari = WarareruKazu % WaruKazu;
            if (Amari == 0) return WaruKazu;
            WarareruKazu = WaruKazu;
            WaruKazu = Amari;
        }
    }

    //試し割りで素数かを判定
    static bool IsPrime(int pTarget)
    {
        if (pTarget == 2) return true;
        if (pTarget % 2 == 0) return false;
        for (int I = 3; I * I <= pTarget; I += 2) {
            if (pTarget % I == 0) return false;
        }
        return true;
    }

    struct JyoutaiDef
    {
        internal int Level;
        internal List<int> VisitedNumList;
    }

    //開始の数値を引数にして、探索し、解候補を返す
    static List<int[]> ExecDFS(int pStaNum)
    {
        var WillReturn = new List<int[]>();

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Level = 0;
        WillPush.VisitedNumList = new List<int>() { pStaNum };
        stk.Push(WillPush);

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //クリア判定
            if (Popped.Level == LimitLevel) {
                WillReturn.Add(Popped.VisitedNumList.ToArray());
                continue;
            }

            WillPush.Level = Popped.Level + 1;
            int CurrNum = Popped.VisitedNumList[Popped.Level];
            foreach (int EachKouho in FriendArrDict[CurrNum]) {
                //再訪不可
                if (Popped.VisitedNumList.Contains(EachKouho))
                    continue;

                //経路にショートカットが存在したら枝切り
                bool WillEdakiri = false;
                for (int J = 0; J <= Popped.Level - 1; J++) {
                    int CheckNum = Popped.VisitedNumList[J];
                    if (FriendArrDict[CheckNum].BinarySearch(EachKouho) >= 0) {
                        WillEdakiri = true;
                        break;
                    }
                }
                if (WillEdakiri) continue;

                WillPush.VisitedNumList = new List<int>(Popped.VisitedNumList);
                WillPush.VisitedNumList.Add(EachKouho);
                stk.Push(WillPush);
            }
        }
        return WillReturn;
    }
}

実行結果

最小のN=55
4,52,39,33,55,35,49,
4,34,51,33,55,35,49,
4,26,39,33,55,35,49,
8,52,39,33,55,35,49,
8,34,51,33,55,35,49,
8,26,39,33,55,35,49,
9,51,34,44,55,35,49,
省略

解説

開始の数値ごとに深さ優先探索してます。
計算量削減で、経路にショートカットが存在したら枝切りしてます。