Educational Codeforces Round 78 (Rated for Div. 2)

이번에도 역시 시간이 없어서 virtual contest로 시험쳤다.

아쉽게 D번에 막혀서 3솔을 했다. 

D번을 틀린 이유는 트리의 필요충분 조건을 잘 몰랐기 때문이었다.

정점 개수 $n$의 그래프가 트리이면 $edge$개수가 $n-1$임은 참인 명제이다

하지만 그 역은 성립하지 않는다.

트리가 되기 위한 필요충분 조건은 다음과 같다.

모든 정점이 연결되어 있고, $edge$개수가 $n-1$ 이면 트리이다.

 

이 점을 놓쳐서 계속 D번 반례가 생겼다.

D.Segment Tree

처음에는 당연히 edge개수만 세서 $n-1$과 비교하려고 했다.

펜윅트리와 $pair(l,r)$의 오름차순으로 정렬한 segment를 이용한 풀이였다.

 

여기서 더 나아가서 연결된 정점 쌍은 저장해놓았다가 dfs를 통해 모든 정점이 연결되어 있는지 확인해야 한다.

정점을 서로서로 연결하기 위해서는 시간복잡도가 $O(N^2)$일 것이라 생각할 수 있지만 $edge$ 개수가 

$n-1$을 넘으면 어차피 tree가 아니기 때문에 넘어가는 그 즉시 멈추면 된다.

따라서 $n$개의 (왼쪽좌표,segment index), (오른쪽좌표,segment index) 를 오름차순으로 정렬하고 현재 탐색하려고 하는 index에 해당하는 r값보다 앞에 있는 정점에 대해 연결상태와 $edge$를 추가하면 된다.($set$ 사용)

 

코드: 68220715