Cod sursa(job #3123890)

Utilizator andreipirjol5Andrei Pirjol andreipirjol5 Data 25 aprilie 2023 20:19:01
Problema Diametrul unui arbore Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;
FILE *fin, *fout;

const int NMAX = 1e4;
vector <int> graph[NMAX + 5];
int n, dist[NMAX + 5], maxim, node_max1, node_max2;
bool viz[NMAX + 5];

void dfs1(int node)
{
    if(dist[node] > maxim)
    {
        maxim = dist[node];
        node_max1 = node;
    }

    viz[node] = 1;
    for(int i = 0; i < graph[node].size(); i++)
    {
        int neigh = graph[node][i];

        if(viz[neigh] == 0)
        {
            dist[neigh] = dist[node] + 1;
            dfs1(neigh);
        }
    }
}

void dfs2(int node)
{
    if(dist[node] > maxim)
    {
        maxim = dist[node];
        node_max2 = node;
    }

    viz[node] = 1;
    for(int i = 0; i < graph[node].size(); i++)
    {
        int neigh = graph[node][i];
        if(viz[neigh] == 0)
        {
            dist[neigh] = dist[node] + 1;
            dfs2(neigh);
        }
    }
}

int get_capete()
{
    dfs1(1);

    memset(viz, 0, sizeof viz);
    memset(dist, 0, sizeof dist);
    maxim = 0;

    dfs2(node_max1);

    return maxim;
}
int cnt, ans[NMAX + 5];

int main()
{
    fin = fopen("darb.in", "r");
    fout = fopen("darb.out", "w");

    int n;
    fscanf(fin, "%d", &n);
    for(int i = 1; i <= n - 1; i++)
    {
        int u, v;
        fscanf(fin, "%d%d", &u, &v);

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    fprintf(fout, "%d", get_capete() + 1);

    fclose(fin);
    fclose(fout);
    return 0;
}