#25437 Connected Towns

재밌고 교육적인 문제

ioi practice의 그래프 문제였다.
사실 함수구현이긴 하지만, interactive문제라고 보는 것이 더 정확할 것이다.

코포에 E번 정도에 나올법한 문제였다.

 

i번 정점의 outdegree를 cnt[i]라고 하자.

우리는 모든 정점에 대해서, cnt[i]가 2이상인지를 확인해야 한다.

어떤 쿼리 query(x,y)를 날리게 되면, cnt[x]가 1 증가하던지, cnt[y]가 1 증가한다.
그렇다면 우리는 어떤 정점이 이미 cnt[i]가 2라면 굳이 이 정점을 이용한 쿼리를 날릴 필요가 없다는 점에 유의하자.
interactor 가 adaptive이기 때문에 query(i,j)를 날리게 되면, cnt[i]를 interactor가 올리게 되면 확정적으로 아무 정보도 얻지 못한 것이 되기 때문이다.

 

따라서 cnt[x]와 cnt[y]가 둘다 2이하인 x,y를 잡고 항상 날리게 되면 총 2N번의 쿼리를 이용해서 모든 정점의 cnt[i]를 2이상으로 만들 수 있다.

그런데 주어지는 쿼리 방식이 그래프 이기 때문에, 동일한 query(x,y)를 2번 날린다고 해서, cnt[x]값이 2 증가하지는 않는다. 따라서 문제를 잘 생각해봐야 하는데, 이 그래프를 트리 처럼 만들어주는 것이 포인트이다.
즉 자신의 부모로 가는 간선을 outgoing edge라고 생각을 하게 되면, 0번 정점부터 n-1번 정점까지 총 n-2개의 쿼리를 통해서 트리를 construct 할 수 있게 된다.

트리를 construct 하게 되면, 루트는 cnt가 0이고 나머지 모든 정점은 cnt가 1이다.

 

따라서 문제는 거의 풀렸다. 루트를 제외한 모든 정점들에 대해서 cnt를 2이상으로 만들어보자. 트리는 이분 그래프이기 때문에, 홀수 layer끼리 쿼리를 날리고 짝수 layer 끼리 쿼리를 날리게 되면, 겹치는 간선은 항상 존재 하지 않는다. 따라서 홀수 layer에서는 최대 1개의 정점, 짝수 layer에서도 마찬가지로 1개의 정점에 cnt가 1이다.

 

즉 최종 상황에 오게 되면, 쿼리는 총 2N-3번 날렸고

out degree가 0인 루트

out degree가 1인 홀수 layer 정점 O

out degree가 1인 짝수 layer 정점 E

이렇게 있게 되는 것이 최악의 경우이다.

이때 루트-O 루트-E O-E 3가지 정점에 대해서 연결 되어 있지 않다면 (쿼리를 날린 적이 없다면) 쿼리를 날려준다.

이때 최악의 경우에는 루트,O,E의 모든 정점의 out degree가 1이 된다.

따라서 루트,O,E모두 아직 확인하지 않은 나머지 정점들을 모두 확인하면서, 최종 degree를 결정해야 한다. 잘못 생각하면 여기서 3N개의 쿼리가 필요하다고 생각할 수 있다.

 

그런데  루트,O,E의 모든 정점의 out degree가 1이 되는 최악의 경우에는 이 3개의 정점이 트리에서 연결 그래프를 이룬다는 점을 주목해라.

 

그렇다면 O와 E에는 이미 나머지 N-3개의 정점을 모두 확인해봤다는 것이다. 

따라서 최대 2(N-3)번의 쿼리가 필요하다.

전체 4N의 쿼리로 해결할 수 있다.

설명이 개판인데 귀찮다...