No.244 ★１のグラフの問題

■■■問題■■■

グラフとは頂点と辺からなるデータ構造のことである。
頂点と頂点の間を辺で繋ぐことで頂点と頂点を結ぶことができる。
頂点と頂点を辺で繋いだ頂点間を自由に移動できる。

いま頂点がN個与えられる。
最初の状態ですべての頂点は辺で繋がっていない。
頂点と頂点を辺で繋ぐときのグラフのルールは次のようなものである。

●辺は必ず異なる頂点間を繋ぐ。
●同じ頂点と頂点の間に2本以上の辺は無い。

最初からある頂点の数Nが与えられるので、
すべての頂点を移動できるように繋ぐ必要のある最少の辺の本数を答えよ。

■■■入力■■■

N

最初からある頂点の数Nが与えられる。2 <= N <= 13

■■■出力■■■

繋ぐ必要のある最少の辺の数を1行で出力せよ。
最後に改行すること。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("2");
            //1
            //頂点0と頂点1の2個の頂点がある。
            //この2つの頂点を1つの辺で繋げば良い。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            //3
            //頂点0と頂点1と頂点2と頂点3がある。
            //例えば、頂点0と頂点1、頂点1と頂点2、頂点2と頂点3を繋ぐ方法がある。
            //別に、頂点0と頂点1、頂点1と頂点2、頂点1と頂点3を繋ぐ方法もある。
            //どちらにしろ繋ぐのに必要な辺の本数は3本である。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("13");
            //12
            //13個の頂点がある。
            //辺を繋いでできるグラフのパターンはたくさんあるが、
            //必要な最少の辺の本数は12本である。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);

        Console.WriteLine(N - 1);
    }
}

解説

最初のノードを代表ノードとして、UnionFindの要領でノードを連結していくと考えれば、
(ノード数-1)が解になります。