[3] 가장 먼 노드

이 문제에는 함정이 존재한다 따라서 SIZE를 20001로 지정한다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

#define SIZE 20001

vector<int> vGraph[SIZE];
vector<int> vCount(SIZE);
bool vis[SIZE];

void DFS(int start)
{
    queue<int> q; q.push(start);
    vis[start] = true;

    while (!q.empty())
    {
        auto front = q.front(); q.pop();

        for (int i = 0; i < vGraph[front].size(); i++)
        {
            auto val = vGraph[front][i];

            if (!vis[val])
            {
                vis[val] = true;
                vCount[val] = vCount[front] + 1;
                q.push(val);
            }
        }
    }
}

int solution(int n, vector<vector<int>> edge)
{
    for (int i = 0; i < edge.size(); i++)
    {
        int a = edge[i][0], b = edge[i][1];
        vGraph[a].push_back(b);
        vGraph[b].push_back(a);
    }
    DFS(1);
    int maxElem = *max_element(vCount.begin(), vCount.end()), ans = 0;
    sort(vCount.begin(), vCount.end(), greater<int>());

    for(const auto& item:vCount)
    {
        if (item == 0)
            break;

        if (item == maxElem)
            ans++;
    }
    return ans;
}