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 |
|
|
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 |