Untitled

mail@pastecode.io avatar
unknown
plain_text
16 days ago
1.4 kB
2
Indexable
Never
#include <iostream>
using namespace std;

const int MAXN = 1000; // Số lượng đỉnh tối đa

int n;
int adj[MAXN][MAXN]; // Ma trận kề
char color[MAXN]; // Mảng trạng thái của đỉnh trong quá trình DFS
int parent[MAXN]; // Mảng lưu đỉnh cha của mỗi đỉnh trong cây DFS

void dfs(int v, int start, bool& found_cycle, int& cycle_start) {
    color[v] = 1;
    for (int u = 0; u < n; u++) {
        if (adj[v][u]) {
            if (color[u] == 0) {
                parent[u] = v;
                dfs(u, start, found_cycle, cycle_start);
            }
            else if (color[u] == 1 && u == start) {
                found_cycle = true;
                cycle_start = u;
            }
        }
    }
    color[v] = 2;
}

void find_cycles() {
    for (int i = 0; i < n; i++) {
        bool found_cycle = false;
        int cycle_start = -1;
        dfs(i, i, found_cycle, cycle_start);
        if (found_cycle) {
            cout << "Cycle found starting from vertex " << cycle_start << ": ";
            int v = cycle_start;
            do {
                cout << v << " ";
                v = parent[v];
            } while (v != cycle_start);
            cout << endl;
        }
    }
}

int main() {
    // Nhập số lượng đỉnh và ma trận kề
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> adj[i][j];

    find_cycles();

    return 0;
}
Leave a Comment