LoginSignup
0

More than 3 years have passed since last update.

ロミオとジュリエット

Posted at

考察

  • 連結で辺がN-1本なので与えられるグラフは木
  • 2頂点間の距離をできるだけ長くしたいので、木の直径を求めればよい

解法

  • 木の直径となるような任意の2頂点を出力する。

コード

#include <bits/stdc++.h>
using namespace std;

const int maxV = 111111;
int N;
vector<int> G[maxV]; // 頂点情報のみのグラフ

// treeDFS(親, 現在地, 根から現在地までの距離, 根からの最大の距離, 根から最大の距離となる頂点
void treeDFS(int from, int current, int dist, int &maxDist, int &maxVertex) {
    // 距離と終点を更新
    if (dist > maxDist) {
        maxDist = dist;
        maxVertex = current;
    }

    for (auto to : G[current]) {
        // 逆流を防ぐ
        if (to == from) continue;
        treeDFS(current, to, dist + 1, maxDist, maxVertex);
    }
}

void getTreeDiameter() {
    int start = 0, end = 0, maxDist = 0;
    treeDFS(-1, start, 0, maxDist, end);
    start = end, end = 0, maxDist = 0;
    treeDFS(-1, start, 0, maxDist, end);
        cout << start + 1 << " " << end + 1 << endl;
}

int main() {
    cin >> N;
    for (int i = 0; i < N-1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    getTreeDiameter();

    return 0;
}

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0