Rage_ant's blog

By Rage_ant, history, 3 hours ago, In English
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adj;  
vector<bool> visited;    

bool dfs(int v, int parent) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u]) {
            if (dfs(u, v)) return true;
        } else if (u != parent) {
            return true;
        }
    }
    return false;
}

bool hasCycle(int n) {
    visited.assign(n, false);
    for (int i = 0; i < n; i++) {
        if (!visited[i] && dfs(i, -1)) {
            return true;
        }
    }
    return false;
}

int main() {
    int n, m;  
    cin >> n >> m;
    adj.resize(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u); 
    }
    
    if (hasCycle(n)) cout << "Cycle found\n";
    else cout << "No cycle\n";
    
    return 0;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it