Submission #311863

---

Source Code Expand

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


class B2
{
    List<int> remaining;
    List<int>[] children;
    int Solve()
    {
        string[] str = Console.ReadLine().Split(' ');
        int n = int.Parse(str[0]);
        int m = int.Parse(str[1]);

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

        for (int i = 0; i < m; i++)
        {
            string[] s = Console.ReadLine().Split(' ');
            int x = int.Parse(s[0]) - 1;
            int y = int.Parse(s[1]) - 1;
            children[x].Add(y);
            children[y].Add(x);
        }

        int need = 0;
        remaining = Enumerable.Range(0, n).ToList();
        while (remaining.Count > 0)
        {
            dfs(remaining.First());
            need++;
        }
        return need - 1;
    }

    void dfs(int node)
    {
        remaining.Remove(node);
        var next = children[node].Intersect(remaining);
        foreach (int index in next)
            dfs(index);
    }

    static void Main(string[] args)
    {
        Console.WriteLine(new B2().Solve());
    }
}

Submission Info

Judge Result