오일러경로2 BOJ 1199 - 오일러 회로 https://www.acmicpc.net/problem/1199 양방향그래프 오일러서킷 코드기록용 오일러서킷 존재하면 출력, 없으면 -1출력 오일러트레일은 무시해야 함. ->차수가 홀수인 정점이 없으면 오일러서킷 존재함 int adj[MAX][MAX], n, deg[MAX]; bool odd; vector ans; void euler(int u) { for (int v = 0; v 0) { adj[u][v]--; adj[v][u]--; euler(v); } } ans.push_back(u); } int main() { FAST; cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++).. 2020. 2. 13. 오일러 경로 '한붓그리기' 로 모든 간선을 칠한다면 그게 바로 오일러 경로 오일러 경로가 존재하려면 1. 출발점=도착점인 경우 (오일러 서킷) 양방향: 모든 정점의 차수가 짝수면 된다. 단방향: 모든 정점의 indegree==outdegree 2. 출발점 != 도착점인 경우 (오일러 트레일) 양방향: 출발점과 도착점의 차수는 홀수고 나머지 정점의 차수는 짝수면 된다. 단방향: outdegree[i]==indegree[i]+1인 점(시작점) 단 한개, indegree[i]==outdegree[i]+1인 점(도착점) 단 한개 존재. 컴포넌트가 여러 개인 경우 당연히 오일러 서킷이 존재하지 않을 거라고 생각할 수 있지만, 컴포넌트의 정점이 하나인 경우 간선이 존재하지 않는다는 점을 유념해야 한다. -> 모든 간선이 하나의.. 2020. 2. 12. 이전 1 다음