Pagini recente » Cod sursa (job #120083) | Cod sursa (job #2927660) | Cod sursa (job #864736) | Cod sursa (job #2586108) | Cod sursa (job #1166667)
// Diametrul unui GRAF - O(N)
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#define Nmax 100099
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
int N,x,y,last,D,d[Nmax];
vector < int > G[Nmax];
bitset < Nmax > viz;
queue < int > Q;
void BFS(int S)
{
for(int i=1;i<=N;++i)viz[i]=d[i]=0;
d[S]=1;
for( Q.push(S) ; !Q.empty() ; Q.pop() )
{
int node=Q.front();
for(vector<int>::iterator it=G[node].begin(); it!=G[node].end(); ++it )
if(!viz[*it])
{
viz[*it]=1 , last=*it;
D=d[*it]=d[node]+1;
Q.push(*it);
}
}
}
int main()
{
f>>N;
for(int i=1;i<N;++i)
f>>x>>y , G[x].push_back(y) , G[y].push_back(x);
BFS(1);
BFS(last);
g<<D<<'\n';
return 0;
}