結果
問題 | No.1390 Get together |
ユーザー |
![]() |
提出日時 | 2021-04-20 11:03:43 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 285 ms / 2,000 ms |
コード長 | 2,155 bytes |
コンパイル時間 | 835 ms |
コンパイル使用メモリ | 107,392 KB |
実行使用メモリ | 40,788 KB |
最終ジャッジ日時 | 2024-07-04 05:16:05 |
合計ジャッジ時間 | 6,838 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System.Linq;using System.Collections.Generic;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]);var box = new int[m];var color = new Dictionary<int, List<int>>();var uf = new UnionFind(n + 1);for (int i = 1; i <= n; i++){line = Console.ReadLine().Trim().Split(' ');var b = int.Parse(line[0]) - 1;var c = int.Parse(line[1]);if (box[b] == 0) box[b] = i;else uf.Unite(box[b], i);if (color.ContainsKey(c)) color[c].Add(i);else{color[c] = new List<int>();color[c].Add(i);}}getAns(color, uf);}static void getAns(Dictionary<int, List<int>> d, UnionFind uf){var count = 0;foreach (var x in d){var cv = x.Value.Count();if (cv > 1){var t = x.Value[0];for (int i = 1; i < cv; i++){if (uf.Root(t) != uf.Root(x.Value[i])){uf.Unite(t, x.Value[i]);count++;}}}}Console.WriteLine(count);}}