네트워크 취약성

네트워크 취약성은 자연재해, 요소 고장, 적대적 공격 같은 여러 장애 상황에서 네트워크 성능이 얼마나 떨어지는지를 나타낸다. 네트워크는 흔히 그래프로 표현되며, 정점은 노드에, 간선은 링크에 각각 대응한다. 그래서 네트워크와 그래프는 같은 뜻으로 쓴다. 연결도는 정점을 지웠을 때 그래프가 연결되지 않거나 정점이 하나만 남게 되는 최소 정점 수로 정의되며, 네트워크 취약성을 재는 가장 중요한 척도다.

하지만 연결도는 정점 제거에 대한 그래프의 저항성을 일부만 반영한다. 그래서 여러 지표가 제안되었고, 그중 토네스(toughness)와 산란수(scattering number)가 가장 널리 쓰인다. 두 지표의 바탕은 정점 $k$개를 제거한 뒤 남는 연결 요소 수의 최댓값이다. $c_k(G)$는 그래프 $G$에서 정확히 $k$개의 정점을 제거했을 때 얻을 수 있는 연결 요소 수의 최댓값을 뜻한다. 주어진 그래프 $G$와 양의 정수 $k$에 대해 $c_k(G)$를 구하는 문제는 계산적으로 어렵다.

하지만 구간 그래프 같은 일부 그래프 클래스에서는 $c_k(G)$를 다항 시간에 구할 수 있다. 구간 그래프는 실수선 위의 (닫힌) 구간들을 교차시킨 그래프다. 두 정점은 대응하는 구간이 서로 교차할 때, 그리고 그때에만 간선으로 이어진다. 이 구간들의 집합을 그래프의 구간 표현이라고 부른다. 그림은 구간 그래프와 그 구간 표현의 예이다.

(a) 구간 그래프	(b) (a) 그래프의 구간 표현

정점이 $n$개인 구간 그래프 $G$의 구간 표현이 주어졌을 때, $k \in \{0, 1, \ldots, n-1\}$인 모든 $c_k(G)$를 계산하는 효율적인 프로그램을 작성하라. 예를 들어 그림 (b)의 구간 표현이 주어지면 $c_0(G), c_1(G), \ldots, c_7(G)$는 차례로 1, 1, 1, 2, 2, 3, 2, 1이다.

첫 줄에 구간의 개수를 나타내는 양의 정수 $n$이 주어진다. $n \le 2{,}000$이다. 이어지는 $n$개의 줄에는 각 구간의 왼쪽 끝점과 오른쪽 끝점이 공백으로 구분되어 주어진다. 모든 끝점은 $-100{,}000{,}000$ 이상 $100{,}000{,}000$ 이하의 정수다.

한 줄에 $n$개의 수 $c_0(G), c_1(G), \ldots, c_{n-1}(G)$를 공백 한 칸으로 구분하여 출력한다.