ABC-016-C 友達の友達

■■■問題■■■

高橋くんはSNSの管理者をしています。
このSNSではユーザ同士が友達という関係で繋がることができます。

高橋くんはそれぞれのユーザの「友達の友達」が何人いるかを調べることにしました。
友達関係が与えられるので、各ユーザの「友達の友達」の人数を求めてください。
ただし、自分自身や友達は、「友達の友達」に含みません。

■■■入力■■■

N M
A1 B1
A2 B2
・
・
・
AM BM

●1行目には、ユーザ数 N(1 <= N <= 10)
  と友達の組の数 M(0 <= M <= N×(N-1)/2) がスペース区切りで与えられる。
●各ユーザには1からNまでのユーザIDが割り当てられている。
●2行目からのM行では、
  友達関係にあるユーザのID Ai,Bi(1 <= Ai < Bi <= N) がスペース区切りで与えられる。
  ただし、i≠j ならば (Ai,Bi)≠(Aj,Bj) を満たす。

■■■出力■■■

各ユーザの友達の友達の人数をユーザIDの小さい順に1行ごと出力せよ。
出力の末尾には改行をつけること。

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

    struct ABPairInfoDef
    {
        internal int A;
        internal int B;
    }

    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 ABPairList = new List<ABPairInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            ABPairInfoDef WillAdd;
            WillAdd.A = wkArr[0];
            WillAdd.B = wkArr[1];
            ABPairList.Add(WillAdd);
        }

        //ワーシャルフロイド法
        int[,] CostArr = new int[N + 1, N + 1];

        for (int I = 1; I <= N; I++) {
            for (int J = 1; J <= N; J++) {
                if (I == J) CostArr[I, J] = 0;
                else CostArr[I, J] = int.MaxValue / 2;
            }
        }

        foreach (ABPairInfoDef EachABPair in ABPairList) {
            CostArr[EachABPair.A, EachABPair.B] = 1;
            CostArr[EachABPair.B, EachABPair.A] = 1;
        }

        for (int K = 1; K <= N; K++) {
            for (int I = 1; I <= N; I++) {
                for (int J = 1; J <= N; J++) {
                    int Cost1 = CostArr[I, J];
                    int Cost2 = CostArr[I, K];
                    int Cost3 = CostArr[K, J];

                    if (Cost1 > Cost2 + Cost3)
                        CostArr[I, J] = Cost2 + Cost3;
                }
            }
        }

        for (int I = 1; I <= N; I++) {
            int Cost2Cnt = 0;
            for (int J = 1; J <= N; J++) {
                if (CostArr[I, J] == 2) Cost2Cnt++;
            }
            Console.WriteLine(Cost2Cnt);
        }
    }
}

解説

まず、ワーシャルフロイド法でノードの組み合わせごとの最短距離を求め、
それから、ノードごとに最短距離が2の訪問ノード数を数えてます。