IOI21 Keys 풀이

어떤 점 x에서 시작해서 방문할 수 있는 점의 집합을 A_x라고 합시다. A_x의 값이 최솟값이라면, A_x의 임의의 원소 y에 대해 A_y = A_x를 만족합니다. 이러한 집합 A_x들을 "최소 집합"이라고 합시다. 구하고자 하는 집합은 최소 집합의 합집합입니다.

 

dfs를 다음과 같은 규칙에 따라 돌려봅시다.

현재 dfs tree를 만들고 있는 상황이라고 생각하고, dfs(v)가 실행중이라고 합시다. v의 서브트리의 원소를 S_v라고 할 때,

 

1. S_v와 S_v의 여집합을 연결하는 간선 중, S_v에서 얻은 key를 이용하여 갈 수 있는 간선을 차례로 확인합니다. (주의: S_v는 원소가 계속 추가됩니다.)

2. 그 간선을 타고 가서 나온 정점 w를 방문한 적이 없다면 dfs(w)를 호출합니다.

 

dfs tree를 다 만들었다고 가정하고, 다음 조건을 만족하는 정점들을 "특별한 정점"이라고 합시다.

조건: S_x에서 S_x의 여집합으로 나가는 간선이 존재하지 않는 정점 x

 

그러면 이제 다음과 같은 재밌는 관찰들을 할 수 있습니다. (증명은 생략합니다.)

관찰 1: 임의의 특별한 정점 x에 대해, S_x = A_x이다.

관찰 2: 임의의 최소집합 A에 대해, A의 원소 중 정확히 1개만 특별한 정점이고, 그 정점은 dfs함수가 집합 A에서 가장 먼저 호출된 점이다.

 

따라서, 모든 특별한 정점을 구한 후, 서브트리의 원소의 개수가 가장 적은 특별한 정점들의 서브트리의 합집합이 구하고자 하는 답이 됩니다.

 

이 풀이에서 가장 까다로운 점이 dfs를 O(N+M)에 구현하는 것인데, 이는 독자에게 연습으로 남겨두겠습니다.

 

수정: 제 코드와 풀이가 틀린 것 같습니다. 비슷한 발상으로 scc를 타잔과 스몰투라지로 구하면 풀 수 있습니다. (23/08/06)