BOJ 1167 트리의 지름

1 개요

BOJ 1167 트리의 지름

• 백준 온라인 저지 1167번 문제
• BOJ 35단계

2 C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
	int num;
	int dist;
};
int V, maxDist, maxNode;
bool visited[100001];
vector<Node> graph[100001];

void dfs(int node, int dist) {
	if (visited[node]) return;
	if (maxDist < dist) {
		maxDist = dist;
		maxNode = node;
	}
	visited[node] = true;
	for (int i=0; i<graph[node].size(); i++) {
		int nnum = graph[node][i].num;
		int ndist = graph[node][i].dist;
		dfs(nnum, ndist + dist);
	}
}

void solve() {
	dfs(1, 0);
	memset(visited, 0, sizeof(visited));
	maxDist = 0;
	dfs(maxNode, 0);
	cout << maxDist << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> V;
	int a, b, dist;
	for (int i=1; i<V+1; i++) {
		cin >> a;
		while(true) {
			cin >> b;
			if (b == -1) break;
			cin >> dist;
			graph[a].push_back({b, dist});
			graph[b].push_back({a, dist});
		}
	}
	solve();
}