Untitled

mail@pastecode.io avatarunknown
c_cpp
20 days ago
1.7 kB
0
Indexable
Never
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Graph {
public:
    int nodes;
    unordered_map<int, vector<int>> adj;

    Graph(int n) {
        nodes = n;
        adj.clear();
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int dfs(int node, int parent, int &maxDist) {
        int maxDepth = 0;
        int secondMaxDepth = 0;

        for (int neighbor : adj[node]) {
            if (neighbor != parent) {
                int depth = dfs(neighbor, node, maxDist) + 1;
                if (depth > maxDepth) {
                    secondMaxDepth = maxDepth;
                    maxDepth = depth;
                } else if (depth > secondMaxDepth) {
                    secondMaxDepth = depth;
                }
            }
        }

        maxDist = max(maxDist, maxDepth + secondMaxDepth);

        return maxDepth;
    }

    int getMaxTime() {
        int maxDist = 0;
        dfs(1, -1, maxDist);  // Start DFS from any arbitrary node (e.g., node 1)
        return maxDist;
    }
};

int getMaxTime(int g_nodes, vector<int> g_from, vector<int> g_to) {
    Graph g(g_nodes);

    for (int i = 0; i < g_from.size(); i++) {
        g.addEdge(g_from[i], g_to[i]);
    }

    return g.getMaxTime();
}

int main() {
    int g_nodes;
    cin >> g_nodes;

    vector<int> g_from(g_nodes - 1);
    vector<int> g_to(g_nodes - 1);

    for (int i = 0; i < g_nodes - 1; i++) {
        cin >> g_from[i] >> g_to[i];
    }

    int result = getMaxTime(g_nodes, g_from, g_to);
    cout << result << endl;

    return 0;
}