문제 158

보완 그래프의 연결 성분

태그 보기

구현

정점이 $N$개이고 간선이 $M$개인 무방향 그래프 $G$가 주어진다. 정점의 번호는 $0$부터 $N-1$까지이다. 자기 루프는 없고 중복 간선은 있을 수 있다.

$G$와 같은 정점들로 이루어지고, 서로 다른 두 정점이 $G$에서 인접하지 않을 때에만 두 정점을 간선으로 잇는 그래프를 $G$의 보완 그래프라고 한다. 보완 그래프의 연결 성분 수를 구해 보자.

입력

첫 번째 줄에 테스트 케이스의 수를 의미하는 정수 $Q$가 주어진다. $(1 \le Q \le 100)$

각 테스트 케이스의 첫 번째 줄에 두 정수 $N$, $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 100\,000; 0 \le M \le 200\,000)$

두 번째 줄부터 $M$개의 줄에 걸쳐 간선의 양 끝 정점 번호 $u$, $v$가 공백으로 구분되어 주어진다. $(0 \le u, v < N; u \ne v)$

전체 테스트 케이스에서 $N$의 합은 $200\,000$ 이하이고 $M$의 합은 $300\,000$ 이하이다.

각 테스트 케이스마다 보완 그래프의 연결 성분 수를 한 줄에 출력한다.

1
1
2

언어