오일러 서킷, 오일러 트레일

출처: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 2

<오일러 서킷(Eulerian circuit)>

그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로

(ex) 종이에서 펜을 떼지 않고 지난 선은 다시 지나지 한붓그리기)

무향, 유향그래프에 대해서 모두 해결 가능

<오일러 서킷이 없는 경우 - 무향>

• 두 개 이상의 컴포넌트가 있으면 오일러 서킷은 존재 할 수 없다.

• 임의 정점과연결된 간선의 수가 홀 수 이면 오일러 서킷은 존재 할 수 없다.

<오일러 서킷이 있는 경우 - 무향>

• 모든 정점이 짝수점이라면 오일러 서킷은 항상 존재한다. 
  (단, 방향 그래프일 경우 들어오는 간선과 나가는 간선의 수가 같아야한다.)

<오일러 트레일이 있는 경우 - 유향>

• 모든 정점의 해당 간선이 indgree = outdegree 

시작점과 끝 점이 같은 경우, 다른 경우

u≠v일 때 v와 연결된 간선의 수는 홀수일 수밖에 없다.

u=v일 때 v와 연결된 간선의 수는 짝수일 수밖에 없다.

<오일러 트레일(Eulerian trail)>

오일러 서킷과 같이 그래프의 모든 간선을 정확히 한 번 지나지만 시작점과 끝점이

다른 경오를 오일러 트레일이라고 한다.

<오일러 트레일을 찾는 방법>

u에서 시작해 v에서 끝나는 경우

u와 v사이에 (v -> u)간선을 하나 추가한 후 오일러 서킷을 찾는다.

이 후 결과에 (v -> u)간선을 삭제하면 오일러 트레일을 얻을 수 있다.

<오일러 트레일이 있는 경우 - 무향>

• 시작점과 끝점을 제외한 모든 점의 간선의 수는 짝수이고 시작점과 끝점의 간선의 수는 홀수이다.

<오일러 트레일이 있는 경우 - 유향>

• 시작지점 indegree  = outdegree +1
  도착지점 indegree + 1 = outdegree
 나머지 정점 indegree = outdegree  



<오일러 소스코드 - ans를 reverse하면 답이 나온다>
<관련 문제 Codeforces #288 div 2 D번 <= 유향 오일러!>

[-] Collapse

void Euler(int here){
    int t1;
    while(!adj[here].empty()) {
        t1 = adj[here].back();
        adj[here].pop_back();
        Euler(t1);
    }
    ans.push_back(S[here][1]);
}