Pagini recente » Cod sursa (job #2410863) | Cod sursa (job #341975) | Cod sursa (job #2730338) | Cod sursa (job #592730) | Cod sursa (job #3294988)
/*
- 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;
}