# ICPC 2019 Asia Regional – Seoul Problem E- Network Vulnerability > 문제은행 : 정보올림피아드&알고리즘

공지   새로운 정올 베타버전이 공개되었습니다.    자세히보기

# 4388 : Network Vulnerability

제한시간
3000 ms
메모리제한
512 MB
해결횟수
0 회
시도횟수
0 회

### 문제

Network vulnerability refers to how much the network performance reduces in various cases of disruptions, such as natural disasters, element failures, or adversarial attacks. A network is frequently represented as a graph, in which the vertices and edges correspond to nodes and links, respectively. So the terms network and graph are used interchangeably here. The connectivity, which is defined to be the minimum number of vertices whose deletion results in a disconnected graph or a one-vertex graph, is recognized as the most important measure to evaluate the vulnerability of a network.

Nonetheless, the connectivity only partly reflects the resistance of a graph to the deletion of vertices. Accordingly, there have been many studies proposing other metrics to account for the network vulnerability, among which the toughness and the scattering number appear to be the most popular. The underlying notion of the toughness and scattering number is the maximum number of connected components resulting from removing k vertices from a graph. Let ck(G) denote the maximum number of connected components obtained by removing exactly k vertices from a graph G. It is unfortunate that given a graph G and a positive integer k, the problem of determining ck(G) is computationally intractable.

For some graph classes like interval graphs, however, ck(G) can be computed in polynomial time. An interval graph is the intersection graph of a family of (closed) intervals on the real line, where two vertices are connected with an edge if and only if their corresponding intervals intersect. The family is usually called an interval representation for the graph. See Figure E.1 for an example of an interval graph and its interval representation. Given an interval representation of an interval graph G with n vertices, your job is to write an efficient running program for computing ck(G) for all k included in {0, 1, … , k − 1}. If the interval representation shown in Figure E.1(b), for example, is given, then ܿc0(G), c1(G), c2(G), c3(G), c4(G), c5(G), c6(G), c7(G) are 1, 1, 1, 2, 2, 3, 2, 1, respectively.​

### 입력형식

Your program is to read from standard input. The first line contains a positive integer n representing the number of intervals, where n ≤ 2,000. In the following n lines, each contains a pair of left and right endpoints of an interval. You may assume that the endpoints, left or right, of intervals are integers between −100,000,000 and 100,000,000, inclusive.

### 출력형식

Your program is to write to standard output. Print exactly one line which contains the sequence ܿc0(G), c1(G), ..., cn-1(G) of n numbers separated by a single space.

```8
3 8
1 8
1 7
1 6
4 8
1 2
3 5
7 8```

### 출력 예 복사하기

`1 1 1 2 2 3 2 1`

```3
-2 -2
-2 7
-2 7```

`1 1 1`

```4
-1 -1
3 4
5 6
7 8```

### 출력 예 복사하기

`4 3 2 1`

```5
1 2
2 3
3 4
6 7
7 8```

### 출력 예 복사하기

`2 3 3 2 1`

### 출처

ICPC 2019 Asia Regional – Seoul Problem E

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP