Cod sursa(job #1673996)

Utilizator sabauandrei98Sabau Andrei sabauandrei98 Data 4 aprilie 2016 11:57:39
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <limits.h>
#include <cmath>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <map>
#include <fstream>
#include <list>
#include <queue>
#include <iomanip>
#include <deque>
#include <set>

using namespace std;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define PI 3.14159265
#define inf (1<<30)
#define mod 1000000007
#define nmax 100005

ifstream f("darb.in");
ofstream g("darb.out");

vector<int> v[nmax];
bool seen[nmax];
int  dist[nmax];
int bnod, dst = 0;

int bfs(int nod)
{
    queue<int> q;
    q.push(nod);

    dist[nod] = 0;
    seen[nod] = 1;

    while(!q.empty())
    {
        int n = q.front();
        q.pop();

        for(int i = 0; i < v[n].size(); i++)
            {
                int vec = v[n][i];
                if(!seen[vec])
                {
                    dist[vec] = dist[n] + 1;
                    seen[vec] = 1;
                    q.push(vec);

                    if(dst < dist[vec])
                    {
                        dst = dist[vec];
                        bnod = vec;
                    }
                }
            }
    }
}

void init(int n)
{
    for(int i = 1; i <=n; i++)
    {
        seen[i] = 0;
        dist[i] = 0;
    }
}


int main()
{
    int n;
    f >> n;

    for(int i = 1; i < n; i++)
    {
        int x,y;
        f >> x >> y;
        v[x].pb(y);
        v[y].pb(x);
    }

    init(n);
    bfs(1);

    init(n);
    bfs(bnod);

    g << dst + 1;


    return 0;
}