結果
問題 | No.2072 Anatomy |
ユーザー |
![]() |
提出日時 | 2022-09-17 03:03:39 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 147 ms / 2,000 ms |
コード長 | 1,562 bytes |
コンパイル時間 | 6,416 ms |
コンパイル使用メモリ | 138,424 KB |
実行使用メモリ | 8,028 KB |
最終ジャッジ日時 | 2024-12-22 00:07:02 |
合計ジャッジ時間 | 8,460 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
#include <cassert>#include <cmath>#include <algorithm>#include <iostream>#include <iomanip>#include <limits.h>#include <map>#include <queue>#include <string.h>#include <vector>using namespace std;typedef long long ll;const int MAX_N = 200000;vector<int> _parent;vector<int> _rank;vector<int> _size;class UnionFind {public:UnionFind(int n) {for (int i = 0; i < n; ++i) {_parent.push_back(i);_rank.push_back(0);_size.push_back(1);}}int find(int x) {if (_parent[x] == x) {return x;} else {return _parent[x] = find(_parent[x]);}}void unite(int x, int y) {x = find(x);y = find(y);if (x == y) return;if (_rank[x] < _rank[y]) {_parent[x] = y;_size[y] += _size[x];} else {_parent[y] = x;_size[x] += _size[y];if (_rank[x] == _rank[y]) ++_rank[x];}}bool same(int x, int y) {return find(x) == find(y);}int size(int x) {return _size[find(x)];}};int main() {int N, M;cin >> N >> M;UnionFind uf(N + 1);vector<int> counter(N + 1, 0);int U[M];int V[M];for (int i = 0; i < M; ++i) {cin >> U[i] >> V[i];}for (int i = M - 1; i >= 0; --i) {int u = U[i];int v = V[i];int p1 = uf.find(u);int p2 = uf.find(v);if (uf.same(u, v)) {counter[p1]++;} else {uf.unite(u, v);int p = uf.find(u);counter[p] = max(counter[p1], counter[p2]) + 1;}}cout << counter[uf.find(1)] << endl;return 0;}