Cod sursa(job #3294988)

Utilizator thinkphpAdrian Statescu thinkphp Data 1 mai 2025 10:49:08
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.05 kb
/*
- rulezi BFS de la nodul 1 si determini nodul cel mai indepartat de acesta , sa-l numim LAST
- este unul din capetele diametrului
-


- a doua parcurgere BFS de la nodul LAST
- resetezi visited
- se ruleaza BFS din nou de la nodul last pentru a gasi cea mai mare dinstanta fata de acest nod
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define FIN "darb.in"
#define FOUT "darb.out"
#define MAXN 1000005

using namespace std;

int num_nodes;
vector<int> List_of_Adj[MAXN];
queue<int> Queue;
bool visited[MAXN];

int last, count[MAXN], diameter = 0;

void read() {

     int num_edges,
         i,
         j;

      ifstream file(FIN);

      file>>num_nodes;

      num_edges = num_nodes - 1;

      for(; num_edges; num_edges--) {

            file>>i>>j;

            List_of_Adj[i].push_back(j);
            List_of_Adj[j].push_back(i);
      }

}

void BFS( int node ) {

     int a_node;

     visited[ node ] = 1;

     Queue.push(node);

     count[ node ] = 1;

     while( !Queue.empty() ) {

            a_node = Queue.front();

            Queue.pop();

            for(vector<int>::iterator i = List_of_Adj[ a_node ].begin(); i != List_of_Adj[ a_node ].end(); i++) {

                              if(!visited[ *i ]) {

                                   visited[ *i ] = 1;

                                   Queue.push( *i );

                                   diameter = count[ *i ] = count[ a_node ] + 1;

                                   last = *i;
                              }
            }
     }

}

void write() {

     ofstream file(FOUT);

     file<<diameter;

     file.close();
}

void print_adj() {

     int i, j;

     for(i = 1; i <= num_nodes; ++i) {

              for(j = 0; j < List_of_Adj[i].size(); ++j) {

                       cout<<List_of_Adj[i][j]<<" ";
              }

              cout<<"\n";


     }
}

int main(int argc, char const *argv[]) {

    read();

    //print_adj();

    BFS( 1 );

    memset(visited, 0, sizeof(visited)); //resetare

    BFS( last );

    write();

    return 0;
}