Cod sursa(job #2659894)

Utilizator DawlauAndrei Blahovici Dawlau Data 17 octombrie 2020 18:50:11
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int maxV = 1e5;

vector <int> adjList[1 + maxV];
vector <int> dp;
int V;
int diameter;

void readGraph(){

    fin >> V;

    for(int e = 1; e < V; ++e){

        int u, v;
        fin >> u >> v;

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

    dp.resize(1 + V);
}

void DFS(int node, int dad){

    dp[node] = 1;

    if(adjList[node].size() == 1 and dad == 0){

        int adj = adjList[node].front();
        DFS(adj, node);

        dp[node] += dp[adj];
        diameter = max(diameter, dp[node]);
    }
    else if(adjList[node].size() == 2 and dad){

        int Max = 0;

        for(const int &adj : adjList[node])
            if(adj != dad){

                DFS(adj, node);
                Max = max(Max, dp[adj]);
            }

        dp[node] += Max;
        diameter = max(diameter, dp[node]);
    }
    else {

        int max1 = 0;
        int max2 = 0;

        for(const int &adj : adjList[node])
            if(adj != dad){

                DFS(adj, node);

                if(dp[adj] >= max1)
                    max2 = max1, max1 = dp[adj];
                else if(dp[adj] > max2)
                    max2 = dp[adj];
            }

        diameter = max(diameter, 1 + max1 + max2);
        dp[node] += max1;
    }

}

int main(){

    readGraph();
    DFS(1, 0);

    fout << diameter << '\n';
}