Cod sursa(job #2708843)

Utilizator ecaterinaEcaterina Stefanescu ecaterina Data 19 februarie 2021 15:09:01
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <fstream>
#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

vector <int> v[100001];
char viz[100001];
int coada[100001];
int d[100001];
int sf, inc;

int main() {
    ifstream fin("darb.in");
    ofstream fout("darb.out");
    
    int n, i, m1, m2, nod, dist, maxi, max;
    
    fin >> n;
    
    for(i=0; i<n-1; i++) {
        fin >> m1 >> m2;
        v[m1].push_back(m2);
        v[m2].push_back(m1);
    }
   
    
    nod = 1;
    viz[nod]=1;
    sf = 1;
    inc = 1;
    d[nod] = 1;
    coada[inc] = nod;
    while(inc <= sf) {
        dist = d[coada[inc]];
        for(i=0; i<v[coada[inc]].size(); i++) {
            if(viz[v[coada[inc]][i]] == 0) {
                sf++;
                coada[sf] = v[coada[inc]][i];
                viz[v[coada[inc]][i]] = 1;
                d[v[coada[inc]][i]] = dist + 1;
            }
        }
        inc++;
    }
    
    max = 0;
    maxi = 0;
    for (i=1; i<=n; i++) {
        if (d[i] > max) {
            max = d[i];
            maxi = i;
        }
    }
    
    for (i=1; i<=n; i++) {
        d[i] = 0;
        viz[i] = 0;
    }
    
    viz[maxi] = 1;
    sf = 1;
    inc = 1;
    d[maxi] = 1;
    coada[inc] = maxi;
    while(inc <= sf) {
        dist = d[coada[inc]];
        for(i=0; i<v[coada[inc]].size(); i++) {
            if(viz[v[coada[inc]][i]] == 0) {
                sf++;
                coada[sf] = v[coada[inc]][i];
                viz[v[coada[inc]][i]] = 1;
                d[v[coada[inc]][i]] = dist + 1;
            }
        }
        inc++;
    }
    
    max = 0;
    for (i=1; i<=n; i++) {
        if (d[i] > max) {
            max = d[i];
        }
    }
    
    fout << max;
    
    
    fin.close();
    fout.close();
    return 0;
    
}