Cod sursa(job #3317231)

Utilizator andreiaramaArama Andrei Robert andreiarama Data 22 octombrie 2025 20:38:28
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream cin("darb.in");
ofstream cout("darb.out");

struct Node {
    vector<Node*> neighbours;
    int dist;
    bool visited=false;
};
Node nodes[100001];
Node* maxNode;
int maxDist;

void dfs(Node* start, int dist=1) {
    if(dist>=maxDist) {
        maxDist=dist;
        maxNode=start;
    }
    start->visited=true;
    for(auto &n:start->neighbours) {
        if(!n->visited) {
            dfs(n, dist+1);
        }
    }
    start->visited=false;
}

int n;
int main() {
    cin>>n;
    for(int i=1;i<=n-1;i++) {
        int a, b;
        cin>>a>>b;
        nodes[a].neighbours.push_back(&nodes[b]);
        nodes[b].neighbours.push_back(&nodes[a]);
    }
    maxDist=0;
    dfs(&nodes[1]);
    maxDist=0;
    dfs(maxNode);
    cout<<maxDist;
    return 0;
}