Pagini recente » Cod sursa (job #2917854) | Cod sursa (job #2745431) | Cod sursa (job #1212154) | Cod sursa (job #798038) | Cod sursa (job #1232228)
#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);
};