Hello 2023 E. Anya's Simultaneous Exhibition

Problem - E - Codeforces

먼저 x가 y를 이긴다라는 것을 x에서 y로 가는 간선이 존재한다고 하자. 그리고 어떤 그래프에서 다른 모든 노드로 갈 수 있는 노드를 후보라고 하자.

 

Lemma 1. 토너먼트의 승자는 최소 한 명은 존재한다. (후보는 무조건 한 명 존재한다.)

Proof. 먼저 n이 1 또는 2일 때를 생각해 보자. 1 또는 2일 때는 무조건 어떤 한 노드는 다른 모든 노드를 방문할 수 있다. 여기서 노드를 하나씩 추가해 보자. 지문에 나온 대로 완전 그래프여야 하기 때문에 노드 하나를 추가할 때마다 기존에 있던 모든 노드와 연결되어야 한다. 여기서 기존에 있던 노드 중에서 모든 노드를 방문할 수 있는 노드를 x라 하자. 새로 추가하는 노드를 y라 했을 때 x 하고 y의 간선을 연결해야 한다. x에서 y로 가는 간선을 연결할 경우 기존 노트 x는 다른 모든 노드로 이동할 수 있게 된다. y에서 x로 가는 간선을 연결할 경우 y에서 모든 노드로 갈 수 있게 된다. 따라서 어떠한 경우든 모든 노드로 갈 수 있는 어떤 한 노드는 무조건 존재하게 된다.

 

Lemma 2. out-degree가 제일 많은 노드는 무조건 후보이다.

Proof. out-degree가 제일 많은 노드를 x라 하자. x가 도달할 수 있는 노드들의 집합을 s1이라 하자. 그러면 x의 out-degree는 |s1|보다 같거나 작다. x가 도달할 수 없는 노드들의 집합은 s2가 존재한다고 가정하자. s2에서 어떤 한 노드를 y라 하자. 완전 그래프이기 때문에 y와 s1에 포함된 어떤 한 노드사이의 간선이 존재해야 한다. y는 s1에 포함된 노드가 도달할 수 없는 노드이기 때문에 y에서 s1에 포함된 모든 노드로 가는 간선이 추가되어야 한다. 그리고 y에서 x로 가는 노드도 추가되어야 하므로 y의 out-degree는 최소 |s1| + 1 이 된다. x보다 y의 out-degree가 더 크게 되므로 s2의 집합은 존재하지 않아야 한다.

 

Lemma 3. out-degree가 w 이상이면 무조건 후보인 w가 존재한다.

Proof. SCC로 묶고 위상정렬을 한 후의 상태를 s1, s2, s3, s4 ,,, sk라 가정하자. s1에 포함된 노드들이 후보들이다. 완전 그래프이기 때문에 s1에 포함된 노드들은 s2 ~ sk에 포함된 노드들로 가는 간선이 무조건 존재한다. 왜냐하면 간선이 반대로 존재하게 된다면 s2 ~ sk에서 s1으로 갈 수 있으므로 가정에 위배된다. |s2| + |s3| +... + |sk| 를 w라 했을 때 s1에 포함된 모든 노드들은 out-degree가 w 이상이 된다.

 

Solution. 먼저 n개 노드의 out-degree가 몇인지 확인한다. 여기서 n개의 연산을 사용하게 된다. 그리고 out-degree가 가장 큰 노드 순서대로 내림차순 정렬을 한다. 먼저 Lemma1과 Lemma2에 의하여 첫 번째 노드는 무조건 후보이다. 이제 두 번째부터 차례대로 보면 된다. 그 노드에서 현재까지 후보로 추가된 노드들로 가는 간선이 한 개라도 존재할 경우 그 노드는 후보이다. Lemma 3에 의하여 어떤 노드가 새로 추가되었을 경우 out-degree가 내림차순으로 노드들을 확인하고 있으므로 현재까지 확인한 모든 노드를 후보로 추가해 준다. 이렇게 모든 노드를 확인하고 나면 모든 후보들이 정해진다.

 

Lemma 4. Soution 대로 진행 하다가 후보인데 현재까지 확인된 후보들로 가는 간선이 존재하지 않고 나중에도 추가되지 않게 되어서 누락되는 경우가 존재한다고 생각할 수 있다. 하지만 이러한 경우는 존재하지 않는다.

Proof. 어떤 후보가 누락되었다고 가정하자. 사실 후보이므로 무조건 현재까지 확인된 후보들로 가는 길은 무조건 존재한다. 무조건 존재하므로 추 후 지금 후보군들에게 직접 연결된 노드가 발견될 것이고 발견이 된다면 Lemma 3에 의하여 현재까지 확인된 모든 노드들은 후보로 추가되게 된다. 따라서 어떤 누락된 후보는 무조건 후보로 추가되게 된다.