빼빼로 나눠주기 2

서브태스크 1 빈칸 $K$개의 모든 $2^K$가지 방향을 열거하고 각 학생이 두 맛을 받는지 검사한다. 시간 복잡도는 $O(2^K NM)$이다.

전체 풀이 각 행과 열을 정점으로 하고, 빈칸 $(i,j)$마다 행 $i$와 열 $j$를 잇는 간선을 만든다. 가로 상자는 간선을 행 정점으로, 세로 상자는 열 정점으로 향하게 하는 것과 같다. 학생이 있는 행과 열을 필수 정점이라 하자. 모든 학생이 두 맛을 받는 조건은 모든 필수 정점의 진입 차수가 양수인 것과 같다.

연결 요소가 트리이면 간선 수가 정점 수보다 하나 적다. 모든 정점이 필수이면 모든 정점에 들어오는 간선을 줄 수 없으므로 불가능하다. 필수가 아닌 정점이 있으면 그것을 루트로 잡고 트리 간선을 자식 방향으로 향하게 한다. 루트 이외의 모든 정점은 들어오는 간선을 얻는다.

연결 요소에 사이클이 있으면 신장 트리에 속하지 않는 간선 하나를 $(r,c)$라 하자. $r$을 루트로 잡아 신장 트리를 자식 방향으로 향하게 하고, 그 간선은 $r$로 향하게 한다. 그러면 루트를 포함한 모든 정점이 들어오는 간선을 얻는다. 다른 간선은 임의로 정해도 된다. 고립 정점도 같은 트리 판정에 포함한다.

따라서 필수 정점으로만 이루어진 트리 연결 요소가 있을 때만 불가능하다. DSU로 신장 숲과 추가 간선을 구하고 각 요소의 루트를 정해 순회하면 구성할 수 있다. 재귀 대신 반복 순회를 사용한다. 시간 복잡도는 $O(NM\alpha(N+M))$, 공간 복잡도는 $O(NM+N+M)$이다.

Solution written by GPT6.1