Submission #311544

---

Source Code Expand

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

class B1
{
    static void Main(string[] args)
    {
        string[] str = Console.ReadLine().Split(' ');
        int n = int.Parse(str[0]);
        int m = int.Parse(str[1]);

        var 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;
        var remaining = new List<int>(Enumerable.Range(0, n));
        while (remaining.Count > 0)
        {
            int start = remaining.First();
            var queue = new Queue<int>(n);
            queue.Enqueue(start);
            while (queue.Count > 0)
            {
                int node = queue.Dequeue();
                remaining.Remove(node);
                var next = children[node].Intersect(remaining);
                foreach (int index in next)
                {
                    queue.Enqueue(index);
                }
            }
            need++;
        }
        Console.WriteLine(need - 1);
        Console.ReadLine();
    }
}

Submission Info

Judge Result