結果
問題 | No.2072 Anatomy |
ユーザー |
|
提出日時 | 2022-09-16 22:25:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 72 ms / 2,000 ms |
コード長 | 2,713 bytes |
コンパイル時間 | 2,276 ms |
コンパイル使用メモリ | 197,776 KB |
最終ジャッジ日時 | 2025-02-07 10:01:27 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h>using namespace std ;#define fast_input_output ios::sync_with_stdio(false); cin.tie(nullptr);typedef long long ll ;typedef long double ld ;typedef pair<ll,ll> P ;typedef tuple<ll,ll,ll> TP ;#define chmin(a,b) a = min(a,b)#define chmax(a,b) a = max(a,b)#define bit_count(x) __builtin_popcountll(x)#define gcd(a,b) __gcd(a,b)#define lcm(a,b) a / gcd(a,b) * b#define rep(i,n) for(int i = 0 ; i < n ; i++)#define rrep(i,a,b) for(int i = a ; i < b ; i++)#define endl "\n"struct UnionFind {private:vector<int> par ; //親vector<int> lank ; //木の深さvector<int> volume ; //構成する集合のサイズvector<int> edge ; //構成する集合の辺の数vector<int> value;public:UnionFind(int n){//n要素で初期化par.resize(n) ;lank.resize(n) ;volume.resize(n) ;edge.resize(n) ;value.resize(n) ;for(int i = 0 ; i < n ; i++){par[i] = i ;lank[i] = 0 ;volume[i] = 1 ;edge[i] = 0 ;value[i] = 0;}}//木の根を求めるint root(int x) {if(par[x] == x) return x ;else return par[x] = root(par[x]) ;}//xとyの属する集合を合併void unite(int x , int y){x = root(x);y = root(y) ;if(x == y) {edge[x]++ ;value[x] = max(value[x],value[y]) + 1;return ;}if(lank[x] < lank[y]){par[x] = y ;volume[y] += volume[x] ;edge[y] += edge[x] + 1 ;value[y] = max(value[x],value[y]) + 1;} else {par[y] = x ;volume[x] += volume[y] ;edge[x] += edge[y] + 1 ;value[x] = max(value[x],value[y]) + 1;if(lank[x] == lank[y]) lank[x]++ ;}}bool same(int x , int y) { return root(x) == root(y) ; }int size(int x) { return volume[root(x)] ; }int edge_num(int x) { return edge[root(x)] ; }int solve(int x) { return value[root(x)] ; }};int n, m ;pair<int,int> E[202020];int main(){fast_input_outputcin >> n >> m ;UnionFind uf(n);rep(i,m){int a, b;cin >> a >> b;a--; b--;E[i] = {a,b};}for(int i = m - 1 ; i >= 0 ; i--){auto [a, b] = E[i];uf.unite(a,b);}int res = 0;rep(i,n) chmax(res,uf.solve(i));cout << res << endl;}