Kiểm tra đồ thị vô hướng chứa chu trình Euler (Eulerian Circuit)

Chu trình Euler (Eulerian circuit) là đường đi Euler bắt đầu và kết thúc tại cùng một đỉnh. Điều kiện:

1. Đồ thị liên thông.
2. Tất cả đỉnh đều có bậc chẵn (odd degree = 0).

Ví dụ code

#include <iostream>
#include <vector>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
    {0,1,1,1,1},
    {1,0,1,0,0},
    {1,1,0,0,0},
    {1,0,0,0,1},
    {1,0,0,1,0}
};

// dfs, isConnected giống bài trước

int hasEulerianCircuit() {
    if (!isConnected()) return 0;
    vector<int> deg(NODE,0);
    int odd = 0;
    for (int i=0; i
Kết quả
Có chu trình Euler