Cod sursa(job #3245826)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 30 septembrie 2024 19:55:02
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
/******************************************************************************

Welcome to GDB Online.
  GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby, 
  C#, OCaml, VB, Perl, Swift, Prolog, Javascript, Pascal, COBOL, HTML, CSS, JS
  Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <iostream>
#include <cstdio>
#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 100000;

vector<int> G[NMAX + 1];
vector<bool> visited1(NMAX + 1), visited2(NMAX + 1);

void dfs(int node, int length, int& maxPath, int& nodeMaxPath, vector<bool>& visited) {
    if (length > maxPath) {
        maxPath = length;
        nodeMaxPath = node;
    }
    visited[node] = true;
    for (int i = 0; i < (int)G[node].size(); i++) {
        int next = G[node][i];
        if (!visited[next])
            dfs(next, length + 1, maxPath, nodeMaxPath, visited);
    }
}


int main()
{
    FILE *fin, *fout;
    fin = fopen("darb.in", "r");
    fout = fopen("darb.out", "w");
    
    int n, x, y;
    fscanf(fin, "%d", &n);
    for (int i = 0; i < n - 1; i++) {
        fscanf(fin, "%d %d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    
    int tmp = -1, node1 = -1, maxLength = -1;
    dfs(1, 0, tmp, node1, visited1);
    dfs(node1, 0, maxLength, tmp, visited2);
    
    fprintf(fout, "%d\n", maxLength + 1);
    fclose(fin);
    fclose(fout);
    return 0;
}