学内ミニプロコン(15/04/02)

procon.cs

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

class Program
{
    // ref: https://github.com/OCTPC/miniprocon/blob/master/miniprocon003/regulation.md
    int n, m;
    List<int>[] g;
    bool[] visit;

    int Solve(System.IO.StringReader stream)
    {
        string[] str = stream.ReadLine().Split(' ');
        n = int.Parse(str[0]);
        m = int.Parse(str[1]);
        g = new List<int>[n];

        for (int i = 0; i < n; i++)
            g[i] = new List<int>();

        for (int i = 0; i < m; i++)
        {
            string[] s = stream.ReadLine().Split(' ');
            int a = int.Parse(s[0]) - 1;
            int b = int.Parse(s[1]) - 1;
            g[a].Add(b);
            g[b].Add(a);
        }

        visit = new bool[n];
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            if (visit[i]) continue;
            dfs(i);
            sum++;
        }

        return sum - 1;
    }

    void dfs(int x)
    {
        visit[x] = true;
        foreach (int i in g[x])
            if (!visit[i]) dfs(i);
    }

    static void Main(string[] args)
    {
        Console.WriteLine(new Program().Solve(new System.IO.StringReader(System.IO.File.ReadAllText(args[0]))));
    }
}