https://www.acmicpc.net/problem/1741
1741번: 반 나누기
첫째 줄 학생들의 수 n과, 서로 메신저 아이디를 알고 있는 학생들 쌍의 수 m이 공백을 사이에 두고 주어진다. (2 ≤ n ≤ 100,000. 1 ≤ m ≤ 2,000,000) 이후 m개의 줄에는 서로 메신저 아이디를 알고 있
www.acmicpc.net
서로 메신저를 모르는 두 학생은 무조건 같은 반에 배정해주어야 한다. 간단하게 생각하면 완전 그래프에서 주어진 M개의 간선들을 빼고 남은 그래프의 간선들로 Union-Find를 돌리고 싶다.
하지만 Naive하게 돌리기엔 간선 수가 O(n^2-m)이라 무조건 시간초과가 난다.
이걸 해결하기 위해 잘 생각해 보면, 연결 상황을 만들기 위해서는 이미 같은 Set에 있는 두 정점 간을 체크하지 않는다면 많아봤자 N-1개의 쌍을 체크함을 알 수 있다. 그리고 그 과정에서 문제에서 주어진 간선들은 선형적으로 방문될것이므로 N+M정도로 시간 내에 돌아갈 것이라고 생각할 수 있다.
그러면 이미 같은 Set에 있는 두 정점을 체크하지 않기 위한 로직을 짜 보자. 같은 컴포넌트의 경우, 그 컴포넌트 내의 하나의 정점에서 시작해 무조건 완전탐색이 가능하고, 여기서 사용되는 트리 형태의 간선만 체크할 것이다.
방문하지 않은 정점을 아무거나 골라 BFS같은 그래프 탐색을 돌릴텐데, 처음에 모든 정점을 List에 넣어 놓고, 그래프 탐색 과정에서 방문이 가능하면 다른 정점에서 이 정점을 확인할 필요가 없다는 것이므로 List에서 제거한다. 이렇게 하면 탐색 트리 내의 간선만 체크함이 보장되고, 완전탐색이므로 문제에서 요구되는 연결 상태 역시 보장된다. 정점을 확인할 필요가 없다고 체크하는 시간 복잡도를 최소화하기 위해 연결 리스트를 사용하였다.
