[백준 1199] 오일러 회로 C++

1199번: 오일러 회로

DFS, 오일러

---

1. 문제 해결 아이디어

 

오일러 서킷

 

이 문제는 오일러 서킷을 구하는 문제이다.

 

위 링크의 알고리즘에 따라서 구현을 하고,

간선정보를 받은 후 정점에 대한 degree가 홀수인 정점이 존재한다면 오일러 서킷을 만들 수 없기 때문에 -1을 출력하면 된다.

---

2. 코드 - 07/27 : 틀린 코드네요 ㅈㅅ 합니다 왜 갑자기 틀렸지 다시 풀어봐야지

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> Eucircuit;
int N, adj[1001][1001], degree[1001];
bool visited[1001];
 
void findEuler(int now){
    visited[now] = true;
    for(int i = 1; i <= N; i++){
        if(!adj[now][i]) continue;
        while(adj[now][i] > 0){
            adj[now][i]--;
            adj[i][now]--;
            findEuler(i);
        }
    }
    Eucircuit.push_back(now);
}
 
bool input(){
    cin >> N;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            cin >> adj[i][j];
            degree[i] += adj[i][j];
        }
        if(degree[i] % 2) return false;
    }
    return true;
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    if(!input()){
        cout << -1;
        return 0;
    }
    
    findEuler(1);
    reverse(Eucircuit.begin(), Eucircuit.end());
    
    for(auto &w : Eucircuit){
        cout << w << " ";
    }
    
    return 0;
}