227번째 문제 - 1967 트리의 지름

트리의 지름은 임의의 한 노드에서 다른 노드까지 거리를 구한 후 가징 멀리있는 노드에서 다시 모든 노드까지 거리를 구한후 가장 멀리 떨어져 있는 노드와의 거리가 지름이 된다.

http://blog.myungwoo.kr/112 

여기에 증명이 잘 되어있다.

양방향 가중치 그래프로 만들고 dfs를 하면서 가장 멀리 떨어진 노드와 그 노드까지 거리를 구한다.

부모가 아닌지만 검사해 dfs 함수를 재귀적으로 호출하는 이유는 트리라서 싸이클이 없으니까 !

소스코드 :

#include <iostream>

#include <map>

#include <vector>

using namespace std;

vector<pair<int,int>> adj[100001];

int res,idx;

void dfs(int now,int parent, int len)

{

if(len>res) res=len,idx=now;

for(auto i=adj[now].begin(); i!=adj[now].end(); i++)

{

if(i->first != parent) dfs(i->first,now,len+i->second);

}

}

int main()

{

int n,dest,len,source;

cin>>n;

while(cin>>source>>dest>>len)

{

adj[source].push_back( pair<int,int>(dest,len));

adj[dest].push_back( pair<int,int>(source,len));

}

dfs(1,0,0);

dfs(idx,0,0);

cout<<res;

}