Untitled
unknown
plain_text
a year ago
1.4 kB
7
Indexable
#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; }
Editor is loading...
Leave a Comment