Submission #1230508


Source Code Expand

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Text;
using System.Text.RegularExpressions;
using System.Linq;
using System.IO;

class Program
{
    static void Main(string[] args)
    {
        new Magatro().Solve();
    }
}

public class Scanner
{
    private StreamReader Sr;

    private string[] S;
    private int Index;
    private const char Separator = ' ';

    public Scanner(Stream source)
    {
        Index = 0;
        S = new string[0];
        Sr = new StreamReader(source);
    }

    private string[] Line()
    {
        return Sr.ReadLine().Split(Separator);
    }

    public string Next()
    {
        string result;
        if (Index >= S.Length)
        {
            S = Line();
            Index = 0;
        }
        result = S[Index];
        Index++;
        return result;
    }
    public int NextInt()
    {
        return int.Parse(Next());
    }
    public double NextDouble()
    {
        return double.Parse(Next());
    }
    public long NextLong()
    {
        return long.Parse(Next());
    }
    public decimal NextDecimal()
    {
        return decimal.Parse(Next());
    }
    public string[] StringArray(int index = 0)
    {
        Next();
        Index = S.Length;
        return S.Skip(index).ToArray();
    }
    public int[] IntArray(int index = 0)
    {
        return StringArray(index).Select(int.Parse).ToArray();
    }
    public long[] LongArray(int index = 0)
    {
        return StringArray(index).Select(long.Parse).ToArray();
    }
    public bool EndOfStream
    {
        get { return Sr.EndOfStream; }
    }
}

public class UnionFind
{
    private int[] Par;
    private int[] Rank;
    public int Cnt;

    public UnionFind(int n)
    {
        Par = (new int[n]).Select((i, index) => index).ToArray();
        Rank = new int[n];
        Cnt = n;
    }

    public int Root(int a)
    {
        if (Par[a] == a) return a;
        else return Root(Par[a]);
    }

    public bool Same(int a, int b)
    {
        return Root(a) == Root(b);
    }

    public void Union(int a, int b)
    {
        a = Root(a);
        b = Root(b);
        if (a != b)
        {
            Cnt--;
            if (Rank[a] < Rank[b])
            {
                Par[a] = b;
            }
            else
            {
                Par[b] = a;
                if (Rank[a] == Rank[b])
                {
                    Rank[a]++;
                }
            }
        }
    }
}

class Magatro
{
    private int N, M;

    public void Solve()
    {
        Scanner scanner = new Scanner(Console.OpenStandardInput());
        N = scanner.NextInt();
        M = scanner.NextInt();

        UnionFind unionfind = new UnionFind(N);

        for (int i = 0; i < M; i++)
        {
            int x = scanner.NextInt() - 1;
            int y = scanner.NextInt() - 1;

            unionfind.Union(x, y);
        }

        Console.WriteLine(unionfind.Cnt - 1);
    }
}

Submission Info

Submission Time
Task B - 道路工事
User mban
Language C# (Mono 4.6.2.0)
Score 100
Code Size 3152 Byte
Status AC
Exec Time 112 ms
Memory 17468 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 22
Set Name Test Cases
Sample sample1.txt, sample2.txt
All 0.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 3.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt
Case Name Status Exec Time Memory
0.txt AC 23 ms 9300 KB
1.txt AC 23 ms 11220 KB
10.txt AC 24 ms 13268 KB
11.txt AC 23 ms 9300 KB
12.txt AC 23 ms 11220 KB
13.txt AC 23 ms 11348 KB
14.txt AC 23 ms 11220 KB
15.txt AC 96 ms 17468 KB
16.txt AC 27 ms 11232 KB
17.txt AC 28 ms 13280 KB
18.txt AC 27 ms 11232 KB
19.txt AC 112 ms 15328 KB
2.txt AC 23 ms 11220 KB
3.txt AC 23 ms 9300 KB
4.txt AC 23 ms 11220 KB
5.txt AC 23 ms 11220 KB
6.txt AC 23 ms 11348 KB
7.txt AC 23 ms 11220 KB
8.txt AC 23 ms 11220 KB
9.txt AC 24 ms 13268 KB
sample1.txt AC 23 ms 13396 KB
sample2.txt AC 23 ms 9172 KB