Pagini recente » Cod sursa (job #1954680) | Cod sursa (job #650810) | Cod sursa (job #1792150) | Cod sursa (job #1778776) | Cod sursa (job #2610198)
#include <bits/stdc++.h>
using namespace std;
#define NMAX 100009
class Task {
public:
void solve() {
read_input();
print_output(get_result());
}
private:
int n;
vector<int> nodes[NMAX];
int parent[NMAX];
void read_input() {
ifstream fin("darb.in");
fin >> n;
for (int i = 1; i < n; ++i) {
int x, y;
fin >> x >> y;
nodes[x].push_back(y);
parent[y] = x;
}
fin.close();
}
int get_result() {
queue<int> q;
q.push(1);
int curr;
while (!q.empty()) {
curr = q.front();
q.pop();
for (int &neigh : nodes[curr]) {
q.push(neigh);
}
}
int result = 0;
vector<int> dist(n + 1, 0);
dfs(curr, dist, result);
return result + 1;
}
void dfs(int curr, vector<int> &dist, int &result) {
result = max(result, dist[curr]);
if (curr != 1 && !dist[parent[curr]]) {
dist[parent[curr]] = dist[curr] + 1;
dfs (parent[curr], dist, result);
}
for (int &i : nodes[curr]) {
if (!dist[i]) {
dist[i] = dist[curr] + 1;
dfs(i, dist, result);
}
}
}
void print_output(int result) {
ofstream fout("darb.out");
fout << result;
fout.close();
}
};
// Please always keep this simple main function!
int main() {
// Allocate a Task object on heap in order to be able to
// declare huge static-allocated data structures inside the class.
Task *task = new Task();
task->solve();
delete task;
return 0;
}