Cod sursa(job #2695562)

Utilizator StefansenNegulescu Stefan Stefansen Data 13 ianuarie 2021 18:26:01
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

queue<int> q;
vector<int> graf[100005];
int n, last, diam, cost[100005];

void BFS(int node)
{
    memset(cost, 0, sizeof(cost));
    q.push(node);
    cost[node] = 1;

    while(!q.empty())
    {
        int aux = q.front();

        for(int i = 0; i < graf[aux].size(); i++)
            if(!cost[graf[aux][i]])
            {
                q.push(graf[aux][i]);
                cost[graf[aux][i]] = cost[aux] + 1;
                diam = cost[graf[aux][i]];
                last = graf[aux][i];
            }

        q.pop();

    }
}



int main()
{
    f >> n;
    for(int i = 1; i < n; i++)
    {
        int x, y;
        f >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
        //cout << x << ' ' << y;
    }
    BFS(1);
    BFS(last);

    g << diam;


    f.close();
    g.close();
    return 0;
}