Cod sursa(job #1706713)

Utilizator alinaioanaAnghel Alina-Ioana alinaioana Data 23 mai 2016 00:45:53
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>


using namespace std;

vector < vector<int> > graph;
vector <bool> visited;
vector <int> cost;

ifstream f("darb.in");
ofstream g("darb.out");
int n,last,diam;

void bfs(int vertex)
{
    if(vertex < 0 || vertex>n) return;
    int element;
    queue<int> q;
    q.push(vertex);
    visited[vertex]=true;
    cost[vertex]=1;
    while(!q.empty())
    {
        element=q.front();
        for(int i=0; i<graph[element].size();i++)
            if(!visited[graph[element][i]])
            {
                q.push(graph[element][i]);
                cost[graph[element][i]]=cost[element]+1;
                visited[graph[element][i]]=true;

                diam=cost[graph[element][i]];
                last=graph[element][i];
            }
        q.pop();
    }
}


int main()
{
    int a,b;
    f>>n;

    graph.resize(n+1);
    cost.resize(n+1, 0);
    visited.resize(n+1,false);

    for(int i=0;i<n-1;i++){
        f>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    bfs(1);
    cout<<last<<" ";

    cost.clear();
    cost.resize(n+1, 0);
    visited.clear();
    visited.resize(n+1,false);

    bfs(last);
    cout<<last<<" ";
    g<<diam;
    cout<<diam<<" ";
    return 0;
}