Cod sursa(job #2700940)

Utilizator cyg_mihaizMIHAI ZARAFIU cyg_mihaiz Data 29 ianuarie 2021 12:44:52
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <bitset>
#include <vector>

using namespace std;
const int NMAX = 100000;

ifstream fin("darb.in");
ofstream fout("darb.out");

bitset<NMAX + 5> viz;
vector<vector<int> > ad(NMAX + 2);

int dist[NMAX + 5],darb;

void first_DFS(int node)
{
    int i;
    viz[node] = 1;
    for(i = 0; i < ad[node].size(); i++)
        if(!viz[ad[node][i]])
        {
            dist[ad[node][i]] = dist[node] + 1;
            first_DFS(ad[node][i]);
        }
}

void second_DFS(int node)
{
    int i;
    viz[node] = 0;
    darb = max(darb, dist[node]);
    for(i = 0; i < ad[node].size(); i++)
        if(viz[ad[node][i]])
        {
            dist[ad[node][i]] = dist[node] + 1;
            second_DFS(ad[node][i]);
        }
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);

    int n,i,a,b,node,maxx = -1;
    fin >> n;
    for(i = 1; i < n; i++)
    {
        fin >> a >> b;
        ad[a].push_back(b);
        ad[b].push_back(a);
    }
    first_DFS(1);
    for(i = 1; i <= n; i++)
        maxx = max(maxx, dist[i]);
    for(i = 1; i <= n; i++)
    {
        if(dist[i] == maxx)
            node = i;
        dist[i] = 0;
    }
    second_DFS(node);
    fout << darb + 1;
    return 0;
}