結果
問題 | No.2418 情報通だよ!Nafmoくん |
ユーザー |
![]() |
提出日時 | 2023-08-21 15:02:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 1,562 bytes |
コンパイル時間 | 624 ms |
コンパイル使用メモリ | 53,840 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-14 12:25:20 |
合計ジャッジ時間 | 1,827 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
/* -*- coding: utf-8 -*-** 2418.cc: No.2418 情報通だよ!Nafmoくん - yukicoder*/#include<cstdio>#include<vector>#include<algorithm>using namespace std;/* constant */const int MAX_N = 100000;const int MAX_N2 = MAX_N * 2;/* typedef */struct UFT {vector<int> links, ranks, sizes;UFT() {}void init(int n) {links.resize(n);for (int i = 0; i < n; i++) links[i] = i;ranks.assign(n, 1);sizes.assign(n, 1);}int root(int i) {int i0 = i;while (links[i0] != i0) i0 = links[i0];return (links[i] = i0);}int rank(int i) { return ranks[root(i)]; }int size(int i) { return sizes[root(i)]; }bool same(int i, int j) { return root(i) == root(j); }int merge(int i0, int i1) {int r0 = root(i0), r1 = root(i1), mr;if (r0 == r1) return r0;if (ranks[r0] == ranks[r1]) {links[r1] = r0;sizes[r0] += sizes[r1];ranks[r0]++;mr = r0;}else if (ranks[r0] > ranks[r1]) {links[r1] = r0;sizes[r0] += sizes[r1];mr = r0;}else {links[r0] = r1;sizes[r1] += sizes[r0];mr = r1;}return mr;}};/* global variables */UFT uft;/* subroutines *//* main */int main() {int n, m;scanf("%d%d", &n, &m);int n2 = n * 2;uft.init(n2);for (int i = 0; i < m; i++) {int a, b;scanf("%d%d", &a, &b);a--, b--;uft.merge(a, b);}int c = 0;for (int u = 0; u < n2; u++)if (u == uft.root(u)) c += uft.size(u) / 2;printf("%d\n", n - c);return 0;}