木の中心(Tree Center)
(tree/tree_center.cpp)

• View this file on GitHub
• Last update: 2026-03-08 22:25:54+09:00

説明

重みなし木の中心と半径を $O(N)$ で求める。 中心は 1 頂点または隣接する 2 頂点になる。

できること

• pair<int, vector<int>> tree_center(const vector<vector<int>>& g) 木の半径と中心頂点列を返す
• 戻り値の first 半径
• 戻り値の second 中心頂点を 1 個または 2 個持つ

使い方

隣接リストを vector<vector<int>> で持って tree_center(g) を呼ぶ。

auto [radius, centers] = tree_center(g);

実装上の補足

直径の両端点を BFS 2 回で求め、直径パスの中央を中心とする。 直径長が偶数なら中心は 1 個、奇数なら中心は 2 個になる。

Code

pair<int, vector<int>> tree_center(const vector<vector<int>> &G) {
    int n = G.size();
    if (n == 0) return {0, {}};

    auto bfs = [&](int s, vector<int> &par) {
        vector<int> dist(n, -1);
        queue<int> q;
        dist[s] = 0;
        par.assign(n, -1);
        q.push(s);
        int far = s;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            if (dist[far] < dist[v]) far = v;
            for (auto &&to : G[v]) {
                if (dist[to] != -1) continue;
                dist[to] = dist[v] + 1;
                par[to] = v;
                q.push(to);
            }
        }
        return pair<int, vector<int>>(far, dist);
    };

    vector<int> par;
    int s = bfs(0, par).first;
    auto [t, dist] = bfs(s, par);

    vector<int> path;
    for (int v = t; v != -1; v = par[v]) path.push_back(v);
    reverse(path.begin(), path.end());

    int diam = dist[t];
    vector<int> centers;
    centers.push_back(path[diam / 2]);
    if (diam & 1) centers.push_back(path[diam / 2 + 1]);
    return {(diam + 1) / 2, centers};
}

/**
 * @brief 木の中心(Tree Center)
 */

#line 1 "tree/tree_center.cpp"
pair<int, vector<int>> tree_center(const vector<vector<int>> &G) {
    int n = G.size();
    if (n == 0) return {0, {}};

    auto bfs = [&](int s, vector<int> &par) {
        vector<int> dist(n, -1);
        queue<int> q;
        dist[s] = 0;
        par.assign(n, -1);
        q.push(s);
        int far = s;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            if (dist[far] < dist[v]) far = v;
            for (auto &&to : G[v]) {
                if (dist[to] != -1) continue;
                dist[to] = dist[v] + 1;
                par[to] = v;
                q.push(to);
            }
        }
        return pair<int, vector<int>>(far, dist);
    };

    vector<int> par;
    int s = bfs(0, par).first;
    auto [t, dist] = bfs(s, par);

    vector<int> path;
    for (int v = t; v != -1; v = par[v]) path.push_back(v);
    reverse(path.begin(), path.end());

    int diam = dist[t];
    vector<int> centers;
    centers.push_back(path[diam / 2]);
    if (diam & 1) centers.push_back(path[diam / 2 + 1]);
    return {(diam + 1) / 2, centers};
}

/**
 * @brief 木の中心(Tree Center)
 */

Back to top page