Untitled
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; }