Cod sursa(job #1658629)

Utilizator vladmatei139Matei Vlad-Cosmin vladmatei139 Data 21 martie 2016 18:08:50
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <time.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stdlib.h>
using namespace std;
int n,m,s;
int nr=0;
vector <int> v;
vector <vector <int> > graph;
void bfs(int vertex)
{
    int element;
    queue <int> q;
    q.push(vertex);
    v[vertex]=nr;
    while(!q.empty())
    {
        element=q.front();
        for(int i=0;i<graph[element].size();i++)
            if(v[graph[element][i]]==-1)
            {
                q.push(graph[element][i]);
                v[graph[element][i]]=v[element]+1;
            }
        q.pop();
    }
}
int main()
{
    srand(time(NULL));
    int i,a,b;
    ifstream f("darb.in");
    f>>n;
    m=n-1;
    s=(rand()%n)+1;
   // s=7;
    graph.resize(n+1);
    v.resize(100005, -1);
    for(i=0;i<m;i++)
        {
            f>>a>>b;
            a--;
            b--;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
    bfs(s-1);
    ofstream g("darb.out");
    int max=-1;
    int poz=1;
    for(i=0;i<n;i++)
        if(v[i]>max)
            max=v[i], poz=i;
    for(i=0;i<=n;i++)
        v[i]=-1;
    nr=0;
    s=poz;
    bfs(s);
    max=-1;
    poz=1;
    for(i=0;i<n;i++)
        if(v[i]>max)
            max=v[i], poz=i;
    g<<max+1;
    return 0;
}