앳코더90 - 003 - Longest Circular Road（★4）

https://atcoder.jp/contests/typical90/tasks/typical90_c

003 - Longest Circular Road（★4）

문제는 파파고를 이용하여 해석했다.

 

N이 주어지고 N-1개의 간선이 주어진다.

(아마 트리일 것이라고 생각)

 

1번에서 시작하고 1번으로 돌아오되 단 하나의 간선을 추가할 수 있을 때 길이를 최대로 하는 값을 출력하라.

 

처음 생각했던 방식은 dfs로 리프노드까지의 길이를 구하는 방법을 생각했는데 예제 3번에 

10
1 2
1 3
2 4
4 5
4 6
3 7
7 8
8 9
8 10

이런 그래프를 커버할수가 없어서 에디토리얼을 참고했다.

 

정답은 최대로 가는 리프노드에서 dfs를 한번 더돌려서 원형으로 만드는 것이다.

위의 그림 같은경우는 9 또는 10에서 dfs를 돌리면 5 또는 6까지 1을 거치면서 갈 수 있기 때문에 해당 값에 간선 추가한 값이 답이 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;

const int INF = 987654321;
const double pi = 3.14159265358979;
const ll MOD = 1000000007;

int N;
vector<int> graph[100002];
int visited[100002];
vector<int> hubo;
int maxi = -1;
int maxvalue = -1;

void dfs(int cur, int bef, int depth)
{
    visited[cur] = depth;

    if (maxvalue < depth)
    {
        maxi = cur;
        maxvalue = depth;
    }

    for (auto i : graph[cur])
    {
        if (i == bef)
            continue;

        if (visited[i])
            continue;

        dfs(i, cur, depth + 1);
    }
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    cin >> N;

    rep(i, N - 1)
    {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    dfs(1, -1, 0);

    int tmp = maxi;
    maxi = -1;
    maxvalue = -1;


    memset(visited, 0, sizeof(visited));
    dfs(tmp, -1, 0);

    int ans = -1;
    for (int i = 0; i <= N; i++)
    {
        ans = max(ans, visited[maxi]);
    }

    cout << ans + 1;

	return 0;
}