結果
問題 | No.2072 Anatomy |
ユーザー |
|
提出日時 | 2023-07-12 10:27:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 139 ms / 2,000 ms |
コード長 | 2,451 bytes |
コンパイル時間 | 1,002 ms |
コンパイル使用メモリ | 108,996 KB |
最終ジャッジ日時 | 2025-02-15 10:01:21 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
/*やってることは再帰DPみたいなもの*/#include<iostream>#include<set>#include<algorithm>#include<vector>#include<string>#include<set>#include<map>#include<numeric>#include<queue>#include<cmath>using namespace std;typedef long long ll;const ll INF=1LL<<60;typedef pair<int,int> P;typedef pair<int,P> PP;const ll MOD=998244353;const double PI=acos(-1);class UnionFind{public:std::vector<int> par;std::vector<int> rank;std::vector<int> sz;//sz[i]で,頂点iが含まれているグループのサイズstd::vector<int> root;UnionFind(int size){rank=std::vector<int>(size+1,0);par = std::vector<int>(size+1,0);std::iota(par.begin(),par.end(),0);//#include<numeric>sz = std::vector<int>(size+1,1);root=std::vector<int>(size+1);std::iota(root.begin(),root.end(),0);}~UnionFind(){std::vector<int>().swap(rank);std::vector<int>().swap(par);std::vector<int>().swap(sz);std::vector<int>().swap(root);}int find(int x){if(par[x]==x)return x;else return par[x] = find(par[x]);}bool issame(int u,int v){return find(u)==find(v);}void merge(int u,int v){u = find(u);v = find(v);if(u==v) return;if(rank[u]<rank[v]) std::swap(u,v);//uの傘下へvが入る//rank[u]>=rank[v]par[v]=u;sz[u]+=sz[v];if(rank[u]==rank[v])rank[u]++;}int size(int u){//頂点uが属すグループの大きさを表す.u=find(u);return sz[u];}std::map<int,std::vector<int>> element(){std::map<int,std::vector<int>> mp;for(int i=0;i<par.size();i++){root[i]=find(i);mp[root[i]].push_back(i);}return mp;}};int main(){int N,M;cin>>N>>M;vector<int> u(M),v(M);for(int i=0;i<M;i++){cin>>u[i]>>v[i];u[i]--;v[i]--;}UnionFind uf(N);vector<int> dp(N,0);for(int i=M-1;i>=0;i--){int a=u[i],b=v[i];if(uf.issame(a,b)){dp[uf.find(a)]=dp[uf.find(a)]+1;}else{int n=max(dp[uf.find(a)],dp[uf.find(b)])+1;uf.merge(a,b);dp[uf.find(a)]=n;}}int ans=dp[uf.find(0)];cout<<ans<<endl;}