레이팅 미적용농부 존의 소 \(N\)마리에는 \(1\)부터 \(N\)까지 번호가 매겨져 있다(\(2\le N\le 16\)). 소들 사이의 친구 관계는 간선 \(M\)개(\(0\le M\le N(N-1)/2\))를 가진 무방향 그래프로 모델링할 수 있다. 두 소가 친구라는 것은 그래프에서 두 소 사이에 간선이 있는 것과 동치이다.
한 번의 연산으로 그래프에서 간선 하나를 추가하거나 제거할 수 있다. 다음 성질이 성립하도록 만들기 위해 필요한 연산의 최소 횟수를 구하시오. 소 \(a\)와 \(b\)가 친구라면, 다른 모든 소 \(c\)에 대해 \(a\)와 \(b\) 중 적어도 하나는 \(c\)와 친구이다.
Problem credits: Benjamin Qi
배점
- 입력 4-13: 증가하는 순서로 각 \(N\in [6, 15]\)마다 입력이 하나씩 있다.
- 입력 14-18: \(N=16\)
Problem credits: Benjamin Qi
첫째 줄에 \(N\)과 \(M\)이 주어진다.
다음 \(M\)개의 줄에 각각 친구 쌍 \(a\)와 \(b\)(\(1\le a
추가하거나 제거해야 하는 간선의 수를 출력한다.
3 1
1 21The network violates the property. We can add one of edges \((2,3)\) or \((1,3)\),
or remove edge \((1,2)\) to fix this.
3 2
1 2
2 30No changes are necessary.
4 4
1 2
1 3
1 4
2 31riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > February > Gold