木の直径を求める

cho(vvi) vviのグラフを入れる

木の直径が返ってくる

int cho(vector<vector<int>>& v){
    int n = v.size();
    vector<int> go(n,-1);
    queue<int> q;
    q.push(0);
    go[0] = 0;
    while(q.size()!=0){
        int pos = q.front();
        q.pop();
        for(int i : v[pos]){
            if(go[i] == -1){
                go[i] = go[pos]+1;
                q.push(i);
            }
        }
    }
    int st = max_element(go.begin(),go.end())-go.begin();
    q.push(st);
    go.assign(n,-1);
    go[st] = 0;
    while(q.size()!=0){
        int pos = q.front();
        q.pop();
        for(int i : v[pos]){
            if(go[i] == -1){
                go[i] = go[pos]+1;
                q.push(i);
            }
        }
    }
    return *max_element(go.begin(),go.end());
}

変に重みがついてる場合

int cho(vector<vector<pair<int,int>>>& v){
    int n = v.size();
    vector<int> go(n,-1);
    queue<int> q;
    q.push(0);
    go[0] = 0;
    while(q.size()!=0){
        int pos = q.front();
        q.pop();
        for(pair<int,int> p : v[pos]){
            if(go[p.first] == -1){
                go[p.first] = go[pos]+p.second;
                q.push(p.first);
            }
        }
    }
    int st = max_element(go.begin(),go.end())-go.begin();
    q.push(st);
    go.assign(n,-1);
    go[st] = 0;
    while(q.size()!=0){
        int pos = q.front();
        q.pop();
        for(pair<int,int> i : v[pos]){
            if(go[i.first] == -1){
                go[i.first] = go[pos]+i.second;
                q.push(i.first);
            }
        }
    }
    return *max_element(go.begin(),go.end());
}

直径になるペアが知りたい場合

pair<int,int> cho(vector<vector<int>>& v){
    int n = v.size();
    vector<int> go(n,-1);
    queue<int> q;
    q.push(0);
    go[0] = 0;
    while(q.size()!=0){
        int pos = q.front();
        q.pop();
        for(int i : v[pos]){
            if(go[i] == -1){
                go[i] = go[pos]+1;
                q.push(i);
            }
        }
    }
    int st = max_element(go.begin(),go.end())-go.begin();
    q.push(st);
    go.assign(n,-1);
    go[st] = 0;
    while(q.size()!=0){
        int pos = q.front();
        q.pop();
        for(int i : v[pos]){
            if(go[i] == -1){
                go[i] = go[pos]+1;
                q.push(i);
            }
        }
    }
    return {st,max_element(go.begin(),go.end()) - go.begin()};
}