Đề 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
- 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 |
15 6 21 2 32 3 43 1 52 4 64 5 72 5
|
|
Sample 2
| Input | Output |
16 6 21 2 32 3 42 5 52 6 65 6 74 3
|
|
Giải
thuat-toan-tim-chu-trinh-euler
1#include<bits/stdc++.h>
2#include<iostream>
3using namespace std;
4using ll = long long;
5
6const int maxN = 100001;
7const int INF = 1e9; // so vo cung
8
9int n, m; // n: so dinh, m: so canh
10set<int> adj[maxN]; // tap hop luu dinh ke
11int degree[maxN]; // bac cua dinh
12
13void inp() {
14 cin >> n >> m;
15 for(int i=0; i<m; i++) {
16 int x, y;
17 cin >> x >> y;
18 adj[x].insert(y);
19 adj[y].insert(x);
20 degree[x]++;
21 degree[y]++;
22 }
23}
24
25void euler(int v) {
26 stack<int> st;
27 vector<int> EC; // Chu trinh Euler
28 st.push(v);
29 while(!st.empty()) {
30 int x = st.top();
31 if(adj[x].size() != 0) {
32 int y = *adj[x].begin();
33 st.push(y);
34 //xoa(x,y)
35 adj[x].erase(y);
36 adj[y].erase(x);
37 }
38 else {
39 st.pop();
40 EC.push_back(x);
41 }
42 }
43 reverse(begin(EC), end(EC));
44 for(int x: EC) {
45 cout << x << ' ';
46 }
47}
48
49int main() {
50 // Chuyen NHAP, XUAT thanh file
51 freopen("lab_7_input.INP", "r", stdin);
52 freopen("lab_7_output.OUT", "w", stdout);
53
54 // INPUT
55 inp();
56
57 // OUTPUT
58 euler(1);
59}