Pagini recente » Borderou de evaluare (job #2340407) | Calcule | Kth Value | Profil Programmming | Cod sursa (job #3361224)
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
const int MAX_N = 100000;
vector<int> adj[MAX_N + 1];
bitset<MAX_N + 1> vis;
int diam, node1, node2;
int n;
struct State
{
int node, dist;
};
inline int max(int x, int y)
{
return (x > y) ? x : y;
}
inline void maxSelf(int& x, int y)
{
x = (x > y) ? x : y;
}
void Read()
{
f >> n;
for(int i = 1; i < n; i++)
{
int x, y;
f >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
}
void BFS(int source, bool id, int& dest)
{
vis[source] = id;
queue<State> q;
q.push({source, 0});
while(!q.empty())
{
State state = q.front();
q.pop();
for(int node : adj[state.node])
if(vis[node] != id)
{
vis[node] = id;
q.push({node, 1 + state.dist});
}
if(q.empty())
{
diam = state.dist;
dest = state.node;
}
}
}
int main()
{
Read();
BFS(1, true, node1);
BFS(node1, false, node2);
g << (diam + 1) << '\n';
f.close();
g.close();
return 0;
}