BOJ 19934 Connecting Supertrees

Connecting Supertrees (IOI 2020 Day1 #2)

 

 

 

문제 설명

- $n$개의 정점이 있다.

- 정점 $i$에서 정점 $j$로 가는 서로 다른 단순경로가 정확히 $p(i, j)$개가 되도록 그래프를 설계할 것이다.

- 이를 만족하는 그래프가 존재하는지 판별하고, 존재한다면 그 중 하나를 구하여라.

 

 

 

존재성 판별 및 그래프 설계

 

일단, 조건을 만족하는 그래프가 존재하는지부터 생각해보자.

96점어치 Subtask에서는 $0 \leq p(i, j) \leq 2$이므로, $0 \leq p(i, j) \leq 2$일 때를 생각해보자.

 

 

- $p(i, j) = 1$에 대한 관찰

 

Lemma 1. 정점 $i$에 대하여 $p(i, j) = 1$인 $j$들의 집합을 $S$라 하자. 그러면 $x, y \in S$인 모든 $x, y$에 대하여 $p(x, y) = 1$이다.

Proof. $p(x, y) \neq 0$임은 자명하다. ($x - i - y$ 경로가 존재하므로, $x - y$ 단순경로도 존재)

$p(x, y) = 2$인 $(x, y)$가 존재한다고 가정하자.

1. $i - x - y$ 단순경로인 경우

   $p(i, y) = 2$인데, $S$의 정의에 의하여 모순이다.

2. $x - i - y$ 단순경로인 경우

   $x - i$ 경로와 $i - y$ 경로가 유일하므로, $p(x, y) = 2$임이 불가능하다.

 

또한, $x, y \in S$인 모든 $x, y$와 임의의 정점 $k$에 대하여 $p(x, k) = p(y, k)$이다.

따라서, 이러한 집합 $S$에 대하여, $S$의 원소들을 일직선의 체인 형태로 이어주고, $S$의 원소 중 임의의 하나를 잡아서 그 하나의 정점에 대해서만 $S$ 외부의 정점과 간선을 이어주면 된다.

- 이후 단계에서는 $S$의 다른 원소들은 전부 없는 것으로 취급한다.

 

 

- $p(i, j) = 2$에 대한 관찰

 

이제 $p(i, j) = 1$인 $(i, j)$쌍은 존재하지 않는다.

Lemma 2. 정점 $i$에 대하여 $p(i, j) = 2$인 $j$들의 집합을 $T$라고 하자. 그러면 $x, y \in T$인 모든 $x$, $y$에 대하여 $p(x, y) = 2$이다.

Proof. $T$의 원소들은 같은 컴포넌트에 존재하기 때문에, $p(x, y) = 0$인 $x, y \in S$는 존재하지 않는다.

 

따라서, 이러한 집합 $T$에 대하여, $T$의 모든 원소들을 하나의 사이클 형태로 이어주면 알맞는 그래프를 만들 수 있다.

 

 

따라서, 앞에서 정의한 집합 $S, T$에 대하여

- $x$, $y \in S$인 모든 $x$, $y$에 대하여, $p(x, y) = 1$

- $x$, $y \in T$인 모든 $x$, $y$에 대하여, $p(x, y) = 2$

를 모두 만족하는지 확인한다면 주어진 입력의 조건에 맞는 그래프를 설계할 수 있다.

 

 

결과적으로, 앞에서 설명한 것과 같이 그래프를 설계하면, 결과 그래프는 다음과 같이 '하나의 컴포넌트에 최대 하나의 사이클이 존재하는 선인장 그래프'의 집합으로 나타낼 수 있다.

 

Figure 1. 최대 하나의 사이클이 존재하는 선인장 그래프의 예시

 

 

 

$p(i, j) = 3$ 인 경우는?

결과적으로 말하자면, $p(i, j) = 3$인 $(i, j)$의 쌍이 존재하는 경우 답은 존재하지 않는다.

 

Figure 2. $p(i, j) = 3$인 경우의 예시

 

위는 $p(i, j) = 3$을 만족하게 만든 그래프이다. 중복 간선이 존재하지 않으므로, 위와 같이 $i$에서 $j$로 가는 동일한 단순 경로 위에 존재하지 않는 두 정점 $x$, $y$가 존재하게 된다.

이 경우, $p(x, y) > 3$ ($x - i - y$, $x - j - y$, $x - i - j - y$, $x - j - i - y$)가 되기 때문에, $p(i, j) = 3$인 $(i, j)$의 쌍이 존재하는 경우 조건을 만족하는 그래프는 존재하지 않게 된다.