Mai intai trebuie sa te autentifici.
Cod sursa(job #1305381)
| Utilizator | Data | 29 decembrie 2014 19:09:54 | |
|---|---|---|---|
| Problema | Diametrul unui arbore | Scor | 20 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 1.22 kb |
#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#define nmax 100001
#define pb push_back
using namespace std;
FILE *f=fopen("darb.in","r"),*g=fopen("darb.out","w");
queue <int> c;
vector <int> l[nmax];
int n,viz[nmax],lg[nmax],last;
void bf()
{
int i,x,k;
c.push(1);
while(!c.empty())
{
k=c.front();
c.pop();
viz[k]=1;
last=k;
for(i=0;i<l[k].size();i++)
{
x=l[k][i];
if(!viz[x])
c.push(x);
}
}
}
int bfl()
{
int i,x,k,diam=0;
c.push(last);
lg[last]=1;
while(!c.empty())
{
k=c.front();
c.pop();
viz[k]=0;
diam=lg[k];
for(i=0;i<l[k].size();i++)
{
x=l[k][i];
if(viz[x])
{
lg[x]=lg[k]+1;
c.push(x);
}
}
}
return diam;
}
int main()
{
int i,j,m;
fscanf(f,"%d %d",&n,&m);
for(i=1;i<=n;i++)
{
int x,y;
fscanf(f,"%d %d",&x,&y);
l[x].pb(y);
l[y].pb(x);
}
fclose(f);
bf();
fprintf(g,"%d",bfl());
fclose(g);
return 0;
}
