Cod sursa(job #1946559)

Utilizator AkrielAkriel Akriel Data 30 martie 2017 10:46:02
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.04 kb
#include <bits/stdc++.h>

/**

                                          `-.`'.-'
                                       `-.        .-'.
                                    `-.    -./\.-    .-'
                                        -.  /_|\  .-
                                    `-.   `/____\'   .-'.
                                 `-.    -./.-""-.\.-      '
                                    `-.  /< (()) >\  .-'
                                  -   .`/__`-..-'__\'   .-
                                ,...`-./___|____|___\.-'.,.
                                   ,-'   ,` . . ',   `-,
                                ,-'   ________________  `-,
                                   ,'/____|_____|_____\
                                  / /__|_____|_____|___\
                                 / /|_____|_____|_____|_\
                                ' /____|_____|_____|_____\
                              .' /__|_____|_____|_____|___\
                             ,' /|_____|_____|_____|_____|_\
,,---''--...___...--'''--.. /../____|_____|_____|_____|_____\ ..--```--...___...--``---,,
                           '../__|_____|_____|_____|_____|___\
      \    )              '.:/|_____|_____|_____|_____|_____|_\               (    /
      )\  / )           ,':./____|_____|_____|_____|_____|_____\             ( \  /(
     / / ( (           /:../__|_____|_____|_____|_____|_____|___\             ) ) \ \
    | |   \ \         /.../|_____|_____|_____|_____|_____|_____|_\           / /   | |
 .-.\ \    \ \       '..:/____|_____|_____|_____|_____|_____|_____\         / /    / /.-.
(=  )\ `._.' |       \:./ _  _ ___  ____  ____ _    _ _ _ _ _  _ __\        | `._.' /(  =)
 \ (_)       )        \/                                            \       (       (_) /
  \    `----'          """"""""""""""""""""""""""""""""""""""""""""""        `----'    /
   \   ____\__                                                              __/____   /
    \ (=\     \                                                            /     /-) /
     \_)_\     \                                                          /     /_(_/
          \     \                                                        /     /
           )     )  _                                                _  (     (
          (     (,-' `-..__                                    __..-' `-,)     )
           \_.-''          ``-..____                  ____..-''          ``-._/
            `-._                    ``--...____...--''                    _.-'
                `-.._                                                _..-'
                     `-..__               AKRIEL               __..-'
                           ``-..____                  ____..-''
                                    ``--...____...--''

*/

using namespace std;

ifstream fin ("darb.in");
ofstream fout ("darb.out");

const int N = 1e5+1;

vector <int> edges[N];

queue <int> Queue;

bool visited[N];

int distances[N];

int totalNodes, diameter, maxPosition;

inline void readVariables(void){
    fin >> totalNodes;
    for ( int origin, destination; fin >> origin >> destination; ){
        edges[origin].push_back(destination);
        edges[destination].push_back(origin);
    }
}

int BFS(int node){
    memset(visited, 0, totalNodes);
    Queue.push(node);
    visited[node] = true;
    distances[node] = 1;
    maxPosition = node;
    diameter = 1;
    for ( int currentNode; Queue.size(); ){
        currentNode = Queue.front();
        Queue.pop();
        for ( auto it : edges[currentNode] ){
            if ( !visited[it] ){
                distances[it] = distances[currentNode] + 1;
                visited[it] = true;
                if ( distances[it] > diameter ){
                    maxPosition = it;
                    diameter = distances[it];
                }
                Queue.push(it);
            }
        }
    }
    return maxPosition;
}

int main(){
    readVariables();
    int first = BFS(1);
    int second = BFS(first);
    fout << diameter;
}