結果

問題 No.2072 Anatomy
コンテスト
ユーザー Nachia
提出日時 2022-09-16 22:42:07
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 56 ms / 2,000 ms
コード長 2,776 bytes
コンパイル時間 3,362 ms
コンパイル使用メモリ 122,868 KB
最終ジャッジ日時 2025-02-07 10:14:33
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "Main.cpp"


#include <vector>
#include <algorithm>
#line 2 "nachia\\set\\dsu.hpp"

#line 5 "nachia\\set\\dsu.hpp"


namespace nachia {
    struct Dsu{
    private:
        std::vector<int> w;
    public:
        Dsu(int n) : w(n, -1) {}
        int leader(int u){
            if(w[u] < 0) return u;
            return w[u] = leader(w[u]);
        }
        int merge(int u, int v){
            u = leader(u);
            v = leader(v);
            if(u == v) return u;
            if(-w[u] < -w[v]) std::swap(u, v);
            else if(w[u] == w[v]) w[u]--;
            w[v] = u;
            return u;
        }
        bool same(int u, int v){
            return leader(u) == leader(v);
        }
    };
} // namespace nachia
#line 6 "Main.cpp"

namespace nachia{

struct MergerTree{
    std::vector<int> parent;
    std::vector<int> weight;
    int node_count = 0;

    MergerTree(int n, std::vector<std::pair<int,int>> edges){
        Dsu dsu(n);
        std::vector<int> root(n);
        for(int i=0; i<n; i++) root[i] = i;
        node_count = n;
        parent.assign(n+edges.size(), -1);
        weight.assign(n+edges.size(), -1);
        for(size_t i=0; i<edges.size(); i++){
            int u = edges[i].first;
            int v = edges[i].second;
            u = dsu.leader(u);
            v = dsu.leader(v);
            if(u == v){
                parent[root[u]] = node_count;
                root[u] = node_count++;
                weight[root[u]] = (int)i;
                continue;
            }
            parent[root[u]] = node_count;
            parent[root[v]] = node_count;
            int r = dsu.merge(u, v);
            root[r] = node_count++;
            weight[root[r]] = (int)i;
        }
    }

    std::vector<int> getAllDepth() const {
        std::vector<int> res(node_count, 0);
        for(int i=node_count-1; i>=0; i--) if(parent[i] != -1) res[i] = res[parent[i]] + 1;
        return res;
    }
};

} // namespace nachia


#include <iostream>
#include <string>
#line 54 "Main.cpp"
#include <queue>
#include <atcoder/modint>

using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(int)(n); i++)

using Modint = atcoder::static_modint<998244353>;


int main(){
    int N, M; cin >> N >> M;
    vector<pair<int,int>> E(M);
    rep(i,M){
        int u,v; cin >> u >> v; u--; v--;
        E[i] = {u,v};
    }
    reverse(E.begin(), E.end());
    nachia::MergerTree mt(N, E);
    auto d = mt.getAllDepth();
    int ans = *max_element(d.begin(), d.end());
    cout << ans << '\n';
    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0