Cod sursa(job #3293913)

Utilizator andrei_botorogeanuBotorogeanu Andrei andrei_botorogeanu Data 13 aprilie 2025 11:51:04
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.89 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>
#include <vector>
#define FIN "darb.in"
#define FOUT "darb.out"
#define MAXN 100003

using namespace std;

int num_nodes;
//STL
vector<int> List_of_adjacency[ MAXN ]; //graful reprezentat prin liste de adiacenta

bool visisted[ MAXN ];

queue<int> Queue;

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_adjacency[ i ].push_back( j );

          List_of_adjacency[ j ].push_back( i );

     }

}

void Display_list_Adjacency() {

      int i,
          j;

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

          cout<<"Nodul "<<i<<" --> ";

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

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

           cout<<"\n";
      }
}
void write() {

   ofstream file( FOUT );

   file<<diameter;

   file.close();
}

void BFS( int node ) {

    int a_node, i;

    visisted[ node ] = 1;

    Queue.push( node );

    count[ node ] = 1;

    while( !Queue.empty() ) {

          a_node = Queue.front();

          Queue.pop();

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

                       if(!visisted[ *i ]) {

                             visisted[ *i ] = 1;

                             Queue.push( *i );

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

                             last = *i;
                       }
          }

    }

}



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

   //citire arbore
  read();
  //afisare arbore
  Display_list_Adjacency();

  BFS( 1 );

  memset( visisted, 0, sizeof( visisted ) );

  BFS( last );

  write();

  return 0;
}