typical90c

初見ダイクストラか？って思ったけどなんかグラフが簡潔過ぎやしないかと違和感

多分自分の知らないやつや！って事で早速解説へ

木の直径:ノード最短距離の最大値

単語はにわかに知っていたが意味は初知り

1.まず適当なノードを選んでそこから全ノードへの最短距離を求める

2.上記で求めた最短距離の最大ノードからもう一度全ノードへの最短距離を求める

3.2回目に求めた最大の最短距離=木の直径

となるらしい

最短距離の求め方はDFSかBFSを2回やれば良いらしいので早速DFS実装

なんかバグらせてソースコード見たらBFS使っててこっちの方がキレイだなと思いBFSに書き直して提出

ちなみにいつもvectorの要素数分だけfor回すときにvec.size()とかやってたけどもっと簡単に書けるらしい

というかむしろvec.size()とかやると遅いらしい

#include<bits/stdc++.h>

using namespace std;

#define INF (1<<28)

int n;

int c[100009];

vector < int > v[100009];

int bfs(int x){

    for(int i=0;i<100009;i++) c[i] = INF;

    queue<int> que;

    int ret = 0;

    que.push(x);

    c[x] = 0;

    while(!que.empty()){

        int now = que.front(); que.pop();

        for(int nxt: v[now]){

            if(c[nxt] == INF){

                que.push(nxt);

                c[nxt] = c[now] + 1;

                ret = max(ret, c[nxt]);

            }

        }

    }

    return ret;

}

int main(){

    cin >> n;

    for(int i=0;i<n-1;i++){

        int a, b;

        cin >> a >> b;

        v[a].push_back(b);

        v[b].push_back(a);

    }

    int ret = bfs(1);

    for(int i=0;i<100009;i++){

        if(c[i] == ret){

            cout << bfs(i) + 1 << endl;

            break;

        }

    }

 

}