레이팅 미적용농부 존에게는 \(N\)마리의 소가 있다 (\(2\le N\le 10^5\)). 소들은 편의상 \(1 \ldots N\)으로 번호가 매겨져 있다.
이 소들 사이에는 \(M\) (\(1\le M\le 2\cdot 10^5\))쌍의 친구 관계가 있다.
어떤 소들의 그룹에서, 그룹 안의 모든 소가 그룹 내부에만 존재하는 친구 관계의 사슬을 통해 그룹 안의 다른 모든 소에 도달할 수 있으면 이 그룹을 "친구 그룹"이라고 부른다 (그룹 밖의 소와 연결된 친구 관계는 아무 영향이 없다). 친구 그룹의 "강도"는 그룹 내에서 그룹 안의 친구 수가 가장 적은 소의 친구 수에 그룹의 소의 수를 곱한 값이다 (마찬가지로, 그룹 밖의 소와 연결된 친구 관계는 이 정의에서 세지 않음에 유의한다).
모든 친구 그룹에 대한 강도의 최댓값을 구하여라.
Problem credits: Benjamin Qi
채점 방식
- \(1\le T\le 3\)인 테스트 케이스 \(T\)는 \(N \le 16\)을 만족한다.
- \(4\le T\le 9\)인 테스트 케이스 \(T\)는 \(N\le 1000\)을 만족한다.
- \(10\le T\le 20\)인 테스트 케이스 \(T\)는 추가 제약이 없다.
Problem credits: Benjamin Qi
첫째 줄에 \(N\)과 \(M\)이 주어진다.
다음 \(M\)개의 줄에는 소 \(u_i\)와 \(v_i\)가 친구임을 나타내는 두 정수 \(u_i\)와 \(v_i\)가 주어진다 (\(1\le u_i,v_i\le N\), \(u_i\neq v_i\)). 같은 소의 순서 없는 쌍은 두 번 이상 주어지지 않는다.
모든 친구 그룹에 대한 강도의 최댓값을 한 줄에 출력한다.
8 10
1 2
1 3
1 4
2 3
2 4
3 4
1 5
2 6
3 7
4 812The maximum strength can be observed to be with the group of cows numbered
\(1, 2, 3, 4\). The minimum number of friends of any cow in this group within the
group is \(3\), so the answer is \(4\cdot 3=12\).
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > December > Gold