Codeforces Global Round 22 #F. Connectivity Addicts

본 대회 때 submission

이렇게 쉬운걸 왜 본대회 때는 못 풀었지 ㅡㅡ...

아마 긴장해서 그런가 보다. E번 같은 유형은 내가 잘 못하는 유형이었는데 빠르게 F로 넘어갔다면 조금 더 침착해서 풀 지 않았을까...

 

일단 $s_c \leq n_c^2$ 라는 조건을 잘 해석해야 한다.

그런데 degree가 큰 정점 부터 살펴본다고 했을 때, x라는 정점에 degree(x)번 쿼리를 날린다고 하면, 우리는 (degree(x)+1)개의 정점으로 이루어진 connected component를 알게된다.

이들을 모두 같은 색으로 색칠하면 항상 조건을 만족한다. 

 

왜나면, degree가 가장 큰 정점을 뽑았기 때문에 $s_c$는 degree(x)(degree(x)+1)이하이고, $n_c$는 (degree(x)+1)(degree(x)+1)이기 때문이다.

 

따라서 다음과 같은 알고리즘을 생각해볼 수 있다.

 

1. degree가 가장 큰 정점 중, 아직 check되지 않은 정점을 고른다.

2. degree(x)번 쿼리를 날리는데, check 되지 않은 정점이었다면, check되었다고 판정해주고  merge한다.

아니라면 merge후 break한다.

3.마지막에 x번 정점의 색은 find(x)로 골라준다.

 

대회 때는 check를 할 필요가 없다고 착각해서 틀렸다... 떡상할 수 있는 기회였는데 아쉬웠다.