結果
問題 | No.2072 Anatomy |
ユーザー |
|
提出日時 | 2022-09-16 22:05:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 96 ms / 2,000 ms |
コード長 | 1,477 bytes |
コンパイル時間 | 2,162 ms |
コンパイル使用メモリ | 197,336 KB |
最終ジャッジ日時 | 2025-02-07 09:34:37 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h> using namespace std; #ifdef _RUTHEN #include <debug.hpp> #else #define show(...) true #endif using ll = long long; #define rep(i, n) for (int i = 0; i < (n); i++) template <class T> using V = vector<T>; struct unionfind { std::vector<int> parents; unionfind() {} unionfind(int n) : parents(n, -1) {} int leader(int x) { return parents[x] < 0 ? x : parents[x] = leader(parents[x]); } bool merge(int x, int y) { x = leader(x), y = leader(y); if (x == y) return false; if (parents[x] > parents[y]) std::swap(x, y); parents[x] += parents[y]; parents[y] = x; return true; } bool same(int x, int y) { return leader(x) == leader(y); } int size(int x) { return -parents[leader(x)]; } void init(int n) { parents.assign(n, -1); } // reset }; /** * @brief UnionFind * @docs docs/data_structure/unionfind.md */ int main() { ios::sync_with_stdio(false); cin.tie(0); int N, M; cin >> N >> M; V<int> A(M), B(M); rep(i, M) { cin >> A[i] >> B[i]; A[i]--, B[i]--; } reverse(A.begin(), A.end()); reverse(B.begin(), B.end()); V<int> t(N); unionfind uf(N); rep(i, M) { int x = uf.leader(A[i]), y = uf.leader(B[i]); int r = max(t[x], t[y]); t[x] = t[y] = r + 1; uf.merge(A[i], B[i]); } int ans = *max_element(t.begin(), t.end()); cout << ans << '\n'; return 0; }