Cod sursa(job #1671690)

Utilizator cuteangel14Carmen Monoranu cuteangel14 Data 2 aprilie 2016 00:20:04
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <vector>
#include<queue>
#include<fstream>
using namespace std;
int n, m, s;
vector<vector <int> > graph;
vector<int> visited;
vector <int> grad;

struct info
{
    int d,elem;
};

int bfs (int vertex)
{
    queue <info> q;
    info element;
    info aux;
    aux.d=0;
    aux.elem=vertex;
    q.push(aux);
    visited[vertex]=0;
    info v;
    int u;
    while(!q.empty())
    {
        element=q.front();
        for(int i=0;i<graph[element.elem].size();i++)
        {
            if(visited[graph[element.elem][i]]==-1)
            {
                aux.d=1+element.d;
                aux.elem=graph[element.elem][i];
                q.push(aux);
                visited[graph[element.elem][i]]=aux.d;
            }
        }
        v=q.back();
        u=v.elem;
        q.pop();
    }
    return u;
}
int main()
{
    int n;
    ifstream f("darb.in");
    ofstream g("darb.out");
    f>>n;
    graph.resize(n);
    visited.resize(n,-1);
    grad.resize(n,0);
    for(int i=1;i<n;i++)
    {
        int x ,y;
        f>>x>>y;
        x--;
        y--;
        grad[x]++;
        grad[y]++;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    int u;
    for(int i=0;i<n;i++)
    {
        if(grad[i]==1)
        {
            u=bfs(i);
            visited.clear();
            visited.resize(n,-1);
            int v;
            v=bfs(u);
            g<<visited[v]+1;
            break;
        }
    }
    f.close();
    g.close();
    return 0;
}