1199

문제가 좀 불친절 한 것 같다. 

여기서 입력이 핵심인데 두 정점 사이에 간선이 여러개 있을 수 있다고 한다. 그런데 간선이 여러개 있는 것을 어떻게 표현할 것인가에 대한 설명은 없다. 

그래서 나는 주어진 간선 이차원 배열에서 입력받는 정수가 두 정점 사이의 간선의 개수라 생각하고 문제를 풀었다.

나머지는 오일러 회로 문제라 생각하면 된다. 오일러 회로의 성립 요건은

모든 정점의 인접한 간선의 수가 짝수여야 한다는것 이걸로 오일러 회로가 성립 하지 않는 경우에 대해서 -1을 출력했고

성립하는 경우 정점 출력 순서는 주위의 간선이 존재하지 않는 것으로 stack을 이용했다.

여기서 속도 문제가 있었는데

그거는 각 노드마다 자신과 인접한 노드를 queue로 저장해서 관리하는 방법으로 해결했다.

그러면 매번 각 노드와 인접한지 아닌지 찾을 필요가 없다.

#include<iostream> #include<cstdio> #include<stack> #include<vector> #include<queue> #include<fstream> using namespace std; int edges[1005][1005]; int endeg[1005]; struct Node{ queue<int> sto; }; Node nodes[1005]; int main() { int N, tmp, start=1005; stack<int> s; ifstream ifp("input.txt"); ifp>>N; //scanf("%d", &N); for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) { ifp>>edges[i][j]; //scanf("%d", &edges[i][j]); endeg[i]+=edges[i][j]; if(edges[i][j]>0) nodes[i].sto.push(j); } for(int i=1; i<=N; i++) { if(endeg[i]%2==1) { printf("-1\n"); return 0; } if(endeg[i]>0) start=min(i, start); } s.push(start); while(!s.empty()) { while(!nodes[s.top()].sto.empty()) { if(edges[s.top()][nodes[s.top()].sto.front()]>0) { edges[s.top()][nodes[s.top()].sto.front()]--; edges[nodes[s.top()].sto.front()][s.top()]--; s.push(nodes[s.top()].sto.front()); } else { nodes[s.top()].sto.pop(); } } if(nodes[s.top()].sto.empty()) { printf("%d ", s.top()); s.pop(); } } printf("\n"); return 0; }