Tìm chu trình đồ thi có hướng DFS dq

#include <iostream>

using namespace std;

const int MAX = 100;
int graph[MAX][MAX];
int color[MAX];  // Sử dụng mảng color để đánh dấu trạng thái của đỉnh
int parent[MAX];
int num_vertices;

bool dfs_cycle_detection(int current) {
    color[current] = 1;  // Đánh dấu đỉnh hiện tại là đang thăm

    for (int i = 0; i < num_vertices; ++i) {
        if (graph[current][i] == 1) {
            if (color[i] == 0) {
                // Nếu đỉnh i chưa được thăm, thăm nó và đệ quy tiếp
                parent[i] = current;
                if (dfs_cycle_detection(i)) {
                    return true;  // Nếu tìm thấy chu trình, trả về true
                }
            } else if (color[i] == 1) {
                // Nếu gặp đỉnh i đang trong quá trình thăm (đã được đánh dấu 1), có chu trình
                return true;
            }
        }
    }

    color[current] = 2;  // Đánh dấu đỉnh hiện tại đã thăm xong
    return false;
}

bool has_cycle() {
    // Đặt tất cả các đỉnh là chưa được thăm (color = 0)
    for (int i = 0; i < num_vertices; ++i) {
        color[i] = 0;
        parent[i] = -1;
    }

    // Kiểm tra từng đỉnh chưa thăm
    for (int i = 0; i < num_vertices; ++i) {
        if (color[i] == 0) {
            if (dfs_cycle_detection(i)) {
                return true;  // Nếu tìm thấy chu trình từ đỉnh i, trả về true
            }
        }
    }

    return false;  // Không tìm thấy chu trình
}

int main() {
    num_vertices = 5;

    int temp_graph[5][5] = {
        {0, 1, 1, 0, 0},
        {0, 0, 1, 0, 0},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0},
    };

    for (int i = 0; i < num_vertices; ++i) {
        for (int j = 0; j < num_vertices; ++j) {
            graph[i][j] = temp_graph[i][j];
        }
    }

    if (has_cycle()) {
        cout << "Do thi co chu trinh." << endl;
    } else {
        cout << "Do thi khong co chu trinh." << endl;
    }

    return 0;
}