結果
問題 | No.2418 情報通だよ!Nafmoくん |
ユーザー |
![]() |
提出日時 | 2023-08-19 10:40:48 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 128 ms / 2,000 ms |
コード長 | 1,583 bytes |
コンパイル時間 | 2,829 ms |
コンパイル使用メモリ | 112,064 KB |
実行使用メモリ | 35,240 KB |
最終ジャッジ日時 | 2024-11-14 12:25:17 |
合計ジャッジ時間 | 5,732 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
コンパイルメッセージ
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 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 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 * 2);for (int i = 0; i < m; i++){string[] line = Console.ReadLine().Trim().Split(' ');var a = int.Parse(line[0]) - 1;var b = int.Parse(line[1]) - 1;uf.Unite(a, b);}var d = new Dictionary<int, int>();for (int i = 0; i < 2 * n; i++){var p = uf.Root(i);if (d.ContainsKey(p)) d[p]++;else d[p] = 1;}var c = 0;foreach (var x in d.Values)if (x % 2 == 1) c++;Console.WriteLine(c / 2);}}