結果
問題 | No.2418 情報通だよ!Nafmoくん |
ユーザー |
|
提出日時 | 2023-08-12 13:43:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 65 ms / 2,000 ms |
コード長 | 1,427 bytes |
コンパイル時間 | 2,034 ms |
コンパイル使用メモリ | 200,752 KB |
最終ジャッジ日時 | 2025-02-16 03:30:03 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;/* thx for Kohenyan (Debug) */struct UnionFind {vector<int> par, rank;//init size NUnionFind(int N) {par.assign(N, int()), rank.assign(N, int());for(int i = 0; i < N; i++) {par[i] = i;rank[i] = 1;}}// Find Lootint find(int x) {if(par[x] == x) {return x;}else {return par[x] = find(par[x]);}}// Unite x and yvoid unite(int x, int y) {x = find(x);y = find(y);if(x == y) return;if(rank[x] < rank[y]) {par[x] = y;rank[y] += rank[x];}else {par[y] = x;rank[x] += rank[y];}}// isSametree?bool same(int x, int y) {return find(x) == find(y);}// size of x's setint size(int x) {return rank[find(x)];}};int main() {int N, M;cin >> N >> M;vector A(M, 0), B(M, 0);for(int i = 0; i < M; i++) cin >> A[i] >> B[i];UnionFind UF(2*N);for(int i = 0; i < M; i++) UF.unite(A[i]-1, B[i]-1);int ans(N);vector seen(2*N, false);for(int i = 0; i < 2*N; i++) {if(seen[UF.find(i)]) continue;else {ans -= UF.size(i) / 2;seen[UF.find(i)] = true;}}cout << ans << endl;return 0;}