Chương 2-Bài 27. Lab 7 - Tìm chu trình Euler

Đề bài

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

5 6
1 2
2 3
3 1
2 4
4 5
2 5

1 2 4 5 2 3 1

Sample 2

6 6 
1 2 
2 3 
2 5
2 6
5 6
4 3

1 2 5 6 2 3 4

• Tool xem đồ thị online: https://csacademy.com/app/graph_editor/

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);
}