트리의 지름

문제 설명이다.

트리의 지름을 구하기 위해서는 어느 한 정점에서 가장 거리가 먼 정점을 찾고, 그 정점에서 가장 먼 거리를 찾으면 된다.

그래서 그냥 dfs 2번을 하면 되는데, 구현하는데 생각보다 오래 걸렸다.

일단 정점 개수가 100000개까지 가능하기 때문에 V*V크기의 배열을 만들어서 간선을 정리할 수가 없다.

그래서 vector를 써야 되는데 다 까먹어서 찾아보면서 코드를 작성했다.

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int, int>> node[100004];
int V;
int check[100004];
int mv=0,mn=0;
void dfs(int num, int dist)
{
    check[num]=1;
    if(dist>mv)
    {
        mv = dist;
        mn = num;
    }
    for(int i=0;i<node[num].size();i++)
    {
        if(check[node[num][i].first]==1) continue;
        dfs(node[num][i].first, dist+node[num][i].second);
    }
}
int main()
{
    scanf("%d",&V);
    for(int i=1;i<=V;i++)
    {
        int s,e,w;
        scanf("%d %d",&s,&e);
        while(e!=-1)
        {
            scanf("%d",&w);
            node[s].push_back(make_pair(e,w));
            node[e].push_back(make_pair(s,w));
            scanf("%d",&e);
        }
    }
    dfs(1,0);
    for(int i=1;i<=V;i++) check[i]=0;
    dfs(mn,0);
    printf("%d",mv);
}

아무튼 작성한 코드는 위와 같고, 그냥 dfs 2번 하면 끝난다.