Cod sursa(job #2640782)

Utilizator mex7Alexandru Valentin mex7 Data 8 august 2020 11:15:24
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");
vector <int> edgesList[100001];
bitset <100001> reached;
int maxx, last;

void addEdge(int v, int w) {
    edgesList[v].push_back(w);
    edgesList[w].push_back(v);
}

void dfs(int current, int sum) {
    for (int i = 0; i < edgesList[current].size(); i++)
        if (!reached[edgesList[current][i]]) {
            reached[edgesList[current][i]] = 1;
            dfs(edgesList[current][i], sum + 1);
        }
    if (sum > maxx) {
        maxx = sum;
        last = current;
    }
}

int main() {
    int numOfVertices, v, w, root = -1;

    fin >> numOfVertices;
    for (int i = 1; i < numOfVertices; i++) {
        fin >> v >> w;
        addEdge(v, w);
    }

    dfs(1, 1);
    maxx = 0;
    reached.reset();
    dfs(last, 1);
    
    fout << maxx;

    return 0;
}