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

#include <iostream>

using namespace std;

const int MAX = 100;
int graph[MAX][MAX];
int color[MAX];
int parent[MAX];
int stack[MAX];
int top = -1;
int num_vertices;

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

    // Đẩy đỉnh bắt đầu vào ngăn xếp và đánh dấu đang thăm (color = 1)
    stack[++top] = start;
    color[start] = 1;

    while (top != -1) {
        int current = stack[top];

        bool found_unvisited = false;

        for (int i = 0; i < num_vertices; ++i) {
            if (graph[current][i] == 1) {
                if (color[i] == 0) {
                    // Đỉnh chưa thăm, đánh dấu và đưa vào ngăn xếp
                    color[i] = 1;
                    parent[i] = current;
                    stack[++top] = i;
                    found_unvisited = true;
                    break;  // Chuyển sang đỉnh i ngay lập tức
                } else if (color[i] == 1) {
                    // Đỉnh đã thăm nhưng chưa kết thúc thăm (vẫn trong ngăn xếp)
                    return true;  // Tìm thấy chu trình
                }
            }
        }

        if (!found_unvisited) {
            // Nếu không tìm thấy đỉnh chưa thăm, đánh dấu đã thăm xong (color = 2)
            color[current] = 2;
            --top;  // Bỏ đỉnh hiện tại ra khỏi ngăn xếp
        }
    }

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

int main() {
    num_vertices = 5;

    int temp_graph[5][5] = {
        {0, 1, 0, 0, 0},
        {0, 0, 1, 0, 0},
        {0, 0, 1, 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];
        }
    }

    bool has_cycle = false;

    for (int i = 0; i < num_vertices; ++i) {
        if (color[i] == 0) {  // Chỉ xét các đỉnh chưa thăm
            has_cycle = dfs_cycle_detection(i);
            if (has_cycle) break;
        }
    }

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

    return 0;
}