Cod sursa(job #2041164)

Utilizator Tataru_AdelinTataru Adelin Tataru_Adelin Data 16 octombrie 2017 21:52:52
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");
void bfs(int nod,queue<int> &q,vector<vector<int>> &path,vector<int> &dist,bitset<100010> &viz)
{
    int now;
    q.push(nod);
    dist[nod]=1;
    viz[nod]=1;
    while(q.size())
    {
        now=q.front();
        q.pop();
        for(int i=0;i<path[now].size();i++)
        {
            if(!viz[path[now][i]])
            {
                viz[path[now][i]]=1;
                dist[path[now][i]]=dist[now]+1;
                q.push(path[now][i]);
            }
        }
    }
}
int main()
{
    int n,x,y;
    fin>>n;
    vector<vector <int>> path(n+5);
    vector<int> dist(n+5);
    bitset<100010> viz;
    queue<int> q;
    for(int i=0;i<n-1;i++)
    {
        fin>>x>>y;
        path[x].push_back(y);
        path[y].push_back(x);
    }


    bfs(1,q,path,dist,viz);
    int M=1;
    for(int i=1;i<=n;i++)
        if(dist[i]>dist[M])
            M=i;
    for(int i=0;i<=n;i++)
    {
        dist[i]=0;
        viz[i]=0;
    }
    bfs(M,q,path,dist,viz);
    for(int i=1;i<=n;i++)
        if(dist[i]>dist[M])
            M=i;

    fout<<M<<'\n';
    return 0;
}