Pagini recente » Istoria paginii runda/24_februarie_simulare_oji_2024_clasa_9/clasament | Cod sursa (job #1887920) | Cod sursa (job #1830659) | Istoria paginii runda/11_martie_simulare_oji_2024_clasa_10 | Cod sursa (job #1666835)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
const int NMAX = 100001;
int n;
vector<int> muchii[NMAX];
vector<int> stiva;
queue<int> coada;
bitset<NMAX> mark;
int last = 0;
unsigned int best = 0;
void citire()
{
in>>n;
int x,y;
for(int i=1;i<n;i++)
{
in>>x>>y;
muchii[x].push_back(y);
muchii[y].push_back(x);
}
in.close();
}
void bfs(int x)
{
mark.reset();
mark.set(x);
coada.push(x);
int y;
while(!coada.empty())
{
y = coada.front();
for(unsigned int i=0;i<muchii[y].size();i++)
if(!mark.test(muchii[y][i]))
{
mark.set(muchii[y][i]);
coada.push(muchii[y][i]);
last = muchii[y][i];
}
coada.pop();
}
}
void dfs(int x)
{
mark.reset();
mark.set(x);
stiva.push_back(x);
int y,ok,target;
while(!stiva.empty())
{
y = stiva.back();
ok = 0;
for(unsigned int i=0;i<muchii[y].size();i++)
if(!mark.test(muchii[y][i]))
{
ok = 1;
target = muchii[y][i];
break;
}
if(ok)
{
stiva.push_back(target);
if(stiva.size() > best)
best = stiva.size();
mark.set(target);
}
else
stiva.pop_back();
}
}
int main()
{
citire();
bfs(1);
dfs(last);
out<<best<<"\n";
out.close();
return 0;
}