Pagini recente » Cod sursa (job #1938573) | Cod sursa (job #1127009) | Cod sursa (job #1178533) | Cod sursa (job #2551443) | Cod sursa (job #3293913)
#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;
}