Pagini recente » Cod sursa (job #3147016) | Cod sursa (job #2936981) | Cod sursa (job #280876) | Cod sursa (job #2519954) | Cod sursa (job #1996218)
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define MAXN 1001
using namespace std;
ifstream fi("darb.in");
ofstream fo("darb.out");
vector <int> vecin[MAXN];
int D[MAXN],n,a,b;
void bfs(int sursa)
{
queue <int> Q;
Q.push(sursa);
while (!Q.empty())
{
int curent=Q.front();
Q.pop();
for (int i=0; i<vecin[curent].size(); i++)
if (D[vecin[curent][i]]==0)
{
D[vecin[curent][i]]=D[curent]+1;
Q.push(vecin[curent][i]);
}
}
}
int main()
{
///cel mai departat nod de un nod oarecare este un capat al celui
///mai lung drum; daca ar exista un nod care nu e capat
///la o distanta mai mare de nodul ales, atunci distanta dintre
///acel nod si unul dintre capetele drumului cel mai lung ar fi
///mai mare decat distanta drumului cel mai lung -> contradictie
fi>>n;
for (int i=0; i<n; i++)
{
fi>>a>>b;
vecin[a].push_back(b);
vecin[b].push_back(a);
}
bfs(1);
int capat=1;
for (int i=2; i<=n; i++)
if (D[i]>D[capat])
capat=i;
memset(D,0,sizeof(D));
bfs(capat);
int maxim=-1;
for (int i=1; i<=n; i++)
maxim=max(maxim,D[i]);
fo<<maxim+1;
fi.close();
fo.close();
return 0;
}