Đề bài

Cho đồ thị vô hướng có trọng số không âm G=<V,E> được biểu diễn dưới dạng danh sách cạnh trọng số. Hãy viết chương trình tìm chu trình Euler

Input

  • Dòng đầu tiên chứa 3 số n, m, s là số đỉnh, số cạnh của đồ thị và đỉnh bắt đầu (1 <= n <= 1000, 1 <= m <= n*(n-1)/2).
  • M dòng tiếp theo, mỗi dòng là 2 số u, v biểu diễn cạnh u, v của đồ thị (1 <= u, v <= n).
  • Ràng buộc: 1 <= n <= 1000; 1 <= m <= n*(n-1)/2; Trọng số các cạnh là số nguyên không âm không vượt quá 100;

Output

  • Ghi ra file văn bản lab_t_output.OUT.

Sample

Input Output 
5 6
1 2
2 3
3 1
2 4
4 5
2 5
 
1 2 4 5 2 3 1

Sample 2

Input Output 
6 6 
1 2 
2 3 
2 5
2 6
5 6
4 3
 
1 2 5 6 2 3 4
 

Giải

  • Thuật toán:
  • Source code:
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
using ll = long long;

const int maxN = 100001;
const int INF = 1e9; // so vo cung

int n, m; // n: so dinh, m: so canh
set<int> adj[maxN]; // tap hop luu dinh ke
int degree[maxN]; // bac cua dinh

void inp() {
  cin >> n >> m;
  for(int i=0; i<m; i++) {
    int x, y;
    cin >> x >> y;
    adj[x].insert(y);
    adj[y].insert(x);
    degree[x]++;
    degree[y]++;
  }
}

void euler(int v) {
  stack<int> st;
  vector<int> EC; // Chu trinh Euler
  st.push(v);
  while(!st.empty()) {
    int x = st.top();
    if(adj[x].size() != 0) {
      int y = *adj[x].begin();
      st.push(y);
      //xoa(x,y)
      adj[x].erase(y);
      adj[y].erase(x);
    }
    else {
      st.pop();
      EC.push_back(x);
    }
  }
  reverse(begin(EC), end(EC));
  for(int x: EC) {
    cout << x << ' ';
  }
}

int main() {
  // Chuyen NHAP, XUAT thanh file
  freopen("lab_7_input.INP", "r", stdin);
  freopen("lab_7_output.OUT", "w", stdout);

  // INPUT
  inp();
  
  // OUTPUT
  euler(1);
}