Cod sursa(job #1232228)

Utilizator thinkphpAdrian Statescu thinkphp Data 22 septembrie 2014 15:18:02
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#define FIN "darb.in"
#define baga push_back
#define FOUT "darb.out"
#define MAXN 100003

using namespace std;

int num_nodes;
vector<int> List_of_Adjacency[ 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_Adjacency[ i ].baga( j );
           List_of_Adjacency[ j ].baga( i );
     }    
};

void BSF(int node) {

     int a_node, 
         i;
 
     visited[ node ] = 1;

     Queue.push( node );

     count[ node ] = 1; 

     while( !Queue.empty() ) {

             a_node = Queue.front();

             Queue.pop();

             for(i = 0; i < List_of_Adjacency[ a_node ].size(); i++) {

                        if( !visited[ List_of_Adjacency[ a_node ][ i ] ] ) {

                             visited[ List_of_Adjacency[ a_node ][ i ] ] = 1;

                             Queue.push( List_of_Adjacency[ a_node ][ i ] );

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

                             last = List_of_Adjacency[ a_node ][ i ];
                        }
             } 
     }   
};

void Adjacency() {

     int i,
         j;

     for(i = 1; i <= num_nodes; 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();
}

int main() {

    read();

    BSF(1);

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

    BSF(last);

    write();


    return(0);
};