Cod sursa(job #2861153)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 3 martie 2022 16:44:22
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define x first
#define y second
#define mod 1000000007
 
using namespace std;
 
int n, m, maxSteps, x, y;
int steps[100100];
vector < int > V[100100];
bitset < 100100 > viz;

void defaultValues() {
	memset(steps, 0, sizeof(steps));
    viz.reset();
}
 
void dfs(int x)
{
	viz[x] = true;
	for (auto it : V[x]) {
		if (!viz[it]) {
            steps[it] = steps[x] + 1;
            maxSteps = max(steps[it], maxSteps);
            dfs(it);
        }  
    }
}

void bfs(int x) {
    queue < int > Q;
    Q.push(x);
    viz[x] = true;

    while (!Q.empty()) {
        int curr = Q.front();
        Q.pop();

        for (auto it : V[curr]) {
            if (!viz[it]) {
                viz[it] = true;

                steps[it] = steps[curr] + 1;
                maxSteps = max(maxSteps, steps[it]);

                Q.push(it);
            }
        }
    }
}

void run(void (*f)(int), ostream& cout) {
    int node = -1;
    f(1);

	for (int i = 1; i <= n; i++) {
		if (steps[i] == maxSteps) {
            node = i;
            break;
        }
    }

    defaultValues();
	f(node);

	cout << 1 + maxSteps;
}
 
int main() {
    ifstream cin("darb.in");
    ofstream cout("darb.out");

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i < n; i++) {
		cin >> x >> y;
		V[x].push_back(y);
		V[y].push_back(x);
    }

    run(dfs, cout);
    return 0;
}