結果
問題 | No.2072 Anatomy |
ユーザー |
![]() |
提出日時 | 2024-01-31 23:28:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 72 ms / 2,000 ms |
コード長 | 2,264 bytes |
コンパイル時間 | 1,951 ms |
コンパイル使用メモリ | 202,496 KB |
最終ジャッジ日時 | 2025-02-19 00:58:58 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using P = pair<ll, ll>;#define rep(i, a, b) for(ll i = a; i < b; ++i)#define rrep(i, a, b) for(ll i = a; i >= b; --i)constexpr ll inf = 4e18;struct SetupIO {SetupIO() {ios::sync_with_stdio(0);cin.tie(0);cout << fixed << setprecision(30);}} setup_io;struct UnionFind {UnionFind(int N): n(N), data(N, -1) {}int merge(int a, int b) {assert(0 <= a and a < n);assert(0 <= b and b < n);int x = leader(a), y = leader(b);if(x == y) return x;if(-data[x] < -data[y]) swap(x, y);data[x] += data[y];data[y] = x;return x;}bool same(int a, int b) {assert(0 <= a and a < n);assert(0 <= b and b < n);return leader(a) == leader(b);}int leader(int a) {assert(0 <= a and a < n);if(data[a] < 0) return a;return data[a] = leader(data[a]);}int size(int a) {assert(0 <= a and a < n);return -data[leader(a)];}vector<vector<int>> groups() {vector<int> leader_buf(n), group_size(n);for(int i = 0; i < n; ++i) {leader_buf[i] = leader(i);++group_size[leader_buf[i]];}vector<vector<int>> result(n);for(int i = 0; i < n; ++i) {result[i].reserve(group_size[i]);}for(int i = 0; i < n; ++i) {result[leader_buf[i]].push_back(i);}result.erase(remove_if(result.begin(), result.end(), [&](const vector<int>& v) { return v.empty(); }), result.end());return result;}private:int n;vector<int> data;};int main(void) {int n, m;cin >> n >> m;vector<int> u(m), v(m);rep(i, 0, m) {cin >> u[i] >> v[i];u[i]--;v[i]--;}UnionFind uf(n);vector<int> ans(n);rrep(i, m - 1, 0) {if(uf.same(u[i], v[i])) {ans[uf.leader(u[i])]++;} else {int cnt = max(ans[uf.leader(u[i])], ans[uf.leader(v[i])]);uf.merge(u[i], v[i]);ans[uf.leader(u[i])] = cnt + 1;}}cout << ans[uf.leader(0)] << '\n';}