[Codeforces Round 1000(Div.2)] - C. Remove Exactly Two

https://codeforces.com/contest/2063/problem/C

Codeforces Round 1000(Div.2) - C. Remove Exactly Two

문제 유형: 그리디, 그래프, 정렬, 트리
시간 제한: 2초
메모리 제한: 256MB
 

문제

You are given a tree∗ of n vertices. You must perform the following operation exactly twice.

• Select a vertex v;

 

• Remove all edges incident to v, and also the vertex v.

 
Please find the maximum number of connected components after performing the operation exactly twice.
Two vertices x and y are in the same connected component if and only if there exists a path from x to y. For clarity, note that the graph with 0 vertices has 0 connected components by definition.
 
n개의 정점을 가진 트리를 받는다. 정확히 두 번 할 수 있다:
정점 v를 고른다.
v에 부속된 모든 간선을 제거하고, v도 없앤다.
이 연산을 두 번해서 나눠지는 연결 컴포넌트의 최대 개수를 구하시오.
두 정점 x와 y간에 경로가 존재하면 연결 컴포넌트입니다.
 

입력

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤10^4). The description of the test cases follows.
The first line of each test case contains a single integer n(2≤n≤2⋅10^5).
Each of the next n−1 lines contains two integers ui and vi, denoting the two vertices connected by an edge (1≤ui,vi≤n, ui≠vi). It is guaranteed that the given edges form a tree.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5.
 
첫째 줄에 테스트케이스의 수가 주어집니다.
첫째 줄에 정수 n을 받습니다.
다음 줄부터 n-1개줄동안 간선의 정보 (u, v)를 받습니다.
입력은 하나의 트리를 구성하도록 보장됩니다.
 

출력

For each test case, output the maximum number of connected components on a separate line.
각 테스트케이스별로 최대 연결 컴포넌트의 수를 각 줄에 구하시오.
 

풀이

Editorial: https://codeforces.com/blog/entry/138593
인접한 두 정점쌍을 지우면 deg[i] + deg[j] - 2개의 연결 컴포넌트가,
인접하지 않은 두 정점쌍을 지우면 deg[i] + deg[j] - 1개의 연결 컴포넌트로 구성된다.
 
입력을 받으면서 차수까지 구해놓고, 복사본을 만들어서 차수를 정렬시킨다.
이제 각 노드 i에 대해서, 다음의 과정을 거친다:
  노드 i와 인접한 노드들의 차수들을 ideg라고 하자. ideg에 자신과 인접한 노드들의 차수를 모두 담는다.
  이제, 정렬된 차수배열 sdeg의 가장 큰 값이 ideg에 있는 경우, 제거해놨다가 복구를 위한 추가 배열에 임시 저장해놓는다.
  현재 정렬된 차수배열에서 가장 큰 요소는 인접하지 않은 정점들 중에서 가장 큰 차수값이다. 이를 mx라 하자.
  인접한 노드들의 각 차수들을 순회하면서, mx에 최대값을 갱신한다. 여기서 1을 미리 빼서 비교하여 -2를 한 것을 고려한다.
  최종적으로 구해진 파트너 노드의 최대차수와 i노드의 차수를 더하고 1을 빼서 최종답의 최대값을 갱신한다.
 
최종적인 값을 출력해주면 된다.
  
 

코드

C++

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<vector<int>> adj(n);
  vector<int> degree(n, 0);

  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
    degree[u]++;
    degree[v]++;
  }

  if (n == 2) {
    cout << "0\n";
    return;
  }

  int ans = 1;
  int mans = 0;
  auto sdeg = degree;
  sort(sdeg.begin(), sdeg.end());
  for (int i = 0; i < n; ++i) {
    ans = degree[i];
    vector<int> ideg;
    for (int v : adj[i]) {
      ideg.emplace_back(degree[v]);
    }
    ideg.emplace_back(degree[i]);
    sort(ideg.begin(), ideg.end(), greater<>());

    vector<int> rem;
    int mx = -1;
    for (int d : ideg) {
      if (sdeg.back() == d) {
        sdeg.pop_back();
        rem.emplace_back(d);
      }
    }
    reverse(rem.begin(), rem.end());

    if (!sdeg.empty()) {
      mx = max(mx, sdeg.back());
    }
    for (int v : adj[i]) {
      mx = max(mx, degree[v] - 1);
    }
    for (int d : rem) {
      sdeg.emplace_back(d);
    }
    mans = max(ans + mx - 1, mans);
  }
  cout << mans << "\n";
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}