Pagini recente » Cod sursa (job #415771) | Cod sursa (job #1291907) | Cod sursa (job #1697229) | Cod sursa (job #334636) | Cod sursa (job #2700940)
#include <fstream>
#include <bitset>
#include <vector>
using namespace std;
const int NMAX = 100000;
ifstream fin("darb.in");
ofstream fout("darb.out");
bitset<NMAX + 5> viz;
vector<vector<int> > ad(NMAX + 2);
int dist[NMAX + 5],darb;
void first_DFS(int node)
{
int i;
viz[node] = 1;
for(i = 0; i < ad[node].size(); i++)
if(!viz[ad[node][i]])
{
dist[ad[node][i]] = dist[node] + 1;
first_DFS(ad[node][i]);
}
}
void second_DFS(int node)
{
int i;
viz[node] = 0;
darb = max(darb, dist[node]);
for(i = 0; i < ad[node].size(); i++)
if(viz[ad[node][i]])
{
dist[ad[node][i]] = dist[node] + 1;
second_DFS(ad[node][i]);
}
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(NULL);
int n,i,a,b,node,maxx = -1;
fin >> n;
for(i = 1; i < n; i++)
{
fin >> a >> b;
ad[a].push_back(b);
ad[b].push_back(a);
}
first_DFS(1);
for(i = 1; i <= n; i++)
maxx = max(maxx, dist[i]);
for(i = 1; i <= n; i++)
{
if(dist[i] == maxx)
node = i;
dist[i] = 0;
}
second_DFS(node);
fout << darb + 1;
return 0;
}