Kiểm tra đồ thị vô hướng chứa đường đi Euler

Đồ thị vô hướng có đường đi Euler khi:

1. Đồ thị liên thông.
2. Số đỉnh có bậc lẻ (odd degree) bằng 0 (Euler circuit) hoặc 2 (Euler path).

Ví dụ code

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

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

void dfs(int u, vector<bool>& vis) {
    vis[u] = true;
    for (int v=0; v
Kết quả
Có đường đi Euler