Cod sursa(job #1658047)

Utilizator Marius_mFMI-M2 Marius Melemciuc Marius_m Data 21 martie 2016 00:11:51
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.59 kb
/*
 * =====================================================================================
 *
 *       Filename:  diameter.cpp
 *
 *    Description:  http://www.infoarena.ro/problema/darb
 *
 *        Version:  1.0
 *        Created:  03/20/2016 23:39:15
 *       Revision:  none
 *       Compiler:  gcc/g++
 *
 *         Author:  Marius-Constantin Melemciuc  
 *          email:  
 *   Organization:  
 *
 * =====================================================================================
 */

#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

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

int getALeaf(int vertex, int n) { 
    if (vertex < 0 || vertex > n - 1) {
        return 0;
    }
    queue<int> q;
    int element, leafNode = vertex; 

    q.push(vertex);
    visited[vertex] = true; 

    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]);
                visited[graph[element][i]] = true;
                leafNode = graph[element][i];
            }
        }    
        q.pop();   
    }
    return leafNode + 1;
}

int getBiggestDistance(int vertex, int n) {
    if (vertex < 0 || vertex > n - 1) {
        return 0;
    }
    queue<int> q;
    int element; 

    q.push(vertex);
    visited2[vertex] = 0; 

    while (!q.empty()) {
        element = q.front();
        for (int i = 0; i < graph[element].size(); i++) {
            if (visited2[graph[element][i]] == -1) {
                q.push(graph[element][i]);
                visited2[graph[element][i]] = visited2[element] + 1;
            }
        }
        q.pop();
    }

    int maxDistance = 0;

    for (auto it = visited2.begin(); it != visited2.end(); it++) {
        if (*it > maxDistance) {
            maxDistance = (*it);
        }
    }
    return maxDistance;
}

int getDiameter(int n) {
    srand(time(NULL));
    int randomNode = rand() % n;
   
    int leafOne = getALeaf(randomNode, n);
    int diameter = getBiggestDistance(leafOne - 1, n);    

    return diameter + 1;
}

int main() {
    ifstream in("darb.in");
    ofstream out("darb.out"); 

    int n, m; 

    in >> n;
    m = n - 1;

    graph.resize(n);
    visited.resize(n, false);
    visited2.resize(n, -1);

    int x, y;
    for (int i = 0; i < m; i++) {
        in >> x >> y;
        x--;
        y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    out << getDiameter(n);

    return 0;
}