Cod sursa(job #1706666)

Utilizator alinaioanaAnghel Alina-Ioana alinaioana Data 22 mai 2016 22:35:12
Problema Diametrul unui arbore Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>


using namespace std;

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

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

void bfs(int vertex)
{
    if(vertex < 0 || vertex>n-1) 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]]==false) {
                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);
    visited.resize(n);
    cost.resize(n);

    while(b!=n-1)
    {
        f>>a>>b;
        a--;
        b--;
        graph[a].push_back(b);
        graph[b].push_back(a);

    }


    bfs(0);
    bfs(last-1);
    g<<diam;

    f.close();
    g.close();

}