double eulerian circuit

존재 조건

차수가 $1$인 정점에서는 들어온 간선을 즉시 되돌아가야 하므로 답이 없다. 반대로 모든 정점의 차수가 $2$ 이상이면 항상 답이 존재한다. 다리가 있어도 가능하다.

회로 구성

각 간선을 두 개로 복제한 다중 그래프에서 Hierholzer 알고리즘으로 오일러 회로를 구한다. 이제 원래 간선을 기준으로 모든 간선을 두 번씩 지난다. 같은 원래 간선을 연속해서 지나는 부분을 유턴이라고 하자. 회로의 마지막과 처음도 이어져 있다고 본다.

유턴 $u\to v\to u$를 하나 고른다. 정점 $v$의 차수가 $2$ 이상이므로 회로에는 $v$의 다른 방문 $x\to v\to y$가 있다. 간선 $uv$의 두 번의 사용이 이미 선택한 유턴에 모두 포함되므로 $x\neq u$이고 $y\neq u$이다. $x=y$일 수는 있다.

두 방문 사이의 $v\to u\to\cdots\to x\to v$ 구간을 뒤집는다. 두 경계의 연결은 $u\to v\to x$와 $u$가 되어 유턴이 아니다. 내부에서는 이동 방향만 뒤집히므로 유턴 여부가 변하지 않는다. 간선별 사용 횟수와 닫힌 보행이라는 성질도 유지된다. 따라서 유턴 수가 적어도 하나 감소한다.

처음 유턴 수는 $M$ 이하이다. 하나의 원래 간선은 유턴 하나에만 사용될 수 있기 때문이다. 유턴 탐색, 같은 정점의 다른 방문 탐색, 구간 뒤집기를 각각 $O(M)$에 구현하면 총 시간은 $O(N+M^2)$, 공간은 $O(N+$이다. 모든 테스트 케이스의 시간도 이하이다. 연결 조건에서 이다.

서브태스크

서브태스크 1은 각 간선의 사용 횟수를 $0,1,2$의 삼진수로 저장하는 완전탐색으로 해결한다. 첫 번째 입력 간선을 한 방향으로 먼저 지난다고 고정해도, 가능한 회로를 회전하고 필요하면 뒤집어 얻을 수 있으므로 해를 잃지 않는다. 현재 정점, 직전 간선, 삼진수 상태를 메모이제이션하면 시간은 $O(NM^2 3^M)$, 공간은 $O(NM{3}^{}$이다. , 이면 충분하다.

서브태스크 2의 연결 그래프는 경로 또는 사이클이다. 경로에는 답이 없고, 사이클은 같은 방향으로 두 바퀴 돌면 된다. 시간과 공간은 $O(N+M)$이다.

서브태스크 3은 위의 유턴 제거 알고리즘을 사용한다.

Solution written by GPT