結果
問題 | No.556 仁義なきサルたち |
ユーザー |
![]() |
提出日時 | 2021-05-01 12:47:31 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 80 ms / 2,000 ms |
コード長 | 2,060 bytes |
コンパイル時間 | 1,696 ms |
コンパイル使用メモリ | 105,728 KB |
実行使用メモリ | 19,912 KB |
最終ジャッジ日時 | 2024-07-19 20:05:15 |
合計ジャッジ時間 | 3,902 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System.Collections.Generic;using static System.Math;using System;public class UnionFind{private int[] data;public UnionFind(int size){data = new int[size];for (int i = 0; i < size; i++) data[i] = -1;}public bool Unite(int x, int y){x = Root(x);y = Root(y);if (x != y){if (data[y] < data[x]){var tmp = y;y = x;x = tmp;}data[x] += data[y];data[y] = x;}return x != y;}public bool IsSameGroup(int x, int y) => Root(x) == Root(y);public int Root(int x) => data[x] < 0 ? x : data[x] = Root(data[x]);public int getMem(int x) => -data[Root(x)];}public class Hello{static void Main(){string[] line = Console.ReadLine().Trim().Split(' ');var n = int.Parse(line[0]);var m = int.Parse(line[1]);getAns(n, m);}static void getAns(int n, int m){var uf = new UnionFind(n + 1);var p = new Dictionary<int, int>();for (int i = 1; i <= n; i++) p[i] = i;for (int i = 0; i < m; i++){string[] line = Console.ReadLine().Trim().Split(' ');var a = int.Parse(line[0]);var b = int.Parse(line[1]);if (uf.IsSameGroup(a, b)) continue;var counta = uf.getMem(a);var countb = uf.getMem(b);if (counta == countb){var ap = p[uf.Root(a)];var bp = p[uf.Root(b)];var tp = Min(ap, bp);p[uf.Root(a)] = tp;p[uf.Root(b)] = tp;}else{if (counta > countb) p[uf.Root(b)] = p[uf.Root(a)];else p[uf.Root(a)] = p[uf.Root(b)];}uf.Unite(a, b);}for (int i = 1; i <= n; i++){Console.WriteLine(p[uf.Root(i)]);}}}