Pagini recente » Cod sursa (job #2588606) | Cod sursa (job #3287888) | Cod sursa (job #2998428) | Cod sursa (job #1078682) | Cod sursa (job #1408719)
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define DIM 100005
vector <int> vf[DIM];
queue <int> q;
int viz[DIM], dist[DIM], grad[DIM];
int nr_vf, capat;
void citeste()
{
ifstream f("darb.in");
f>>nr_vf;
int x, y;
for(int i = 0; i < nr_vf-1; i++)
{
f>>x>>y;
vf[x].push_back(y);
vf[y].push_back(x);
grad[x]++;
grad[y]++;
}
}
int isArb()
{
int s = 0;
for(int i = 1; i <= nr_vf; i++)
s+=grad[i];
if(s!=2*(nr_vf-1))
return 0;
return 1;
}
void bf(int start)
{
memset(viz, 0, DIM*sizeof(int));
memset(dist, 0, DIM*sizeof(int));
int nod;
q.push(start);
dist[start] = 1;
while(!q.empty())
{
nod = q.front();
viz[nod] = 1;
for(unsigned int i = 0; i < vf[nod].size(); i++)
if(!viz[vf[nod][i]])
{
viz[vf[nod][i]] = 1;
q.push(vf[nod][i]);
dist[vf[nod][i]] = dist[nod]+1;
capat = vf[nod][i];
}
q.pop();
}
}
int main()
{
citeste();
if(!isArb())
{
cout<<"Nu e arbore";
return 0;
}
bf(1);
bf(capat);
ofstream g("darb.out");
g<<dist[capat];
return 0;
}