Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Graphs

Detect Cycle in an Undirected Graph

Medium · Graphs · Asked at Amazon, Microsoft, Samsung, Flipkart

Print YES if the undirected graph contains a cycle, otherwise NO. There are no self-loops or repeated edges.

Input

First line: n m. Next m lines: u v — an undirected edge (nodes are 1..n).

Output

YES or NO.

Constraints

DFS that remembers the parent, or DSU: an edge joining two nodes already in the same set closes a cycle.

Example 1

Input

5 4
1 2
2 3
3 1
4 5

Output

YES

Example 2

Input

4 3
1 2
2 3
3 4

Output

NO

Hints

  1. Disjoint Set Union: process edges one by one, merging the sets of their endpoints.
  2. If an edge connects two nodes that are already in the same set, there was another path between them — that edge closes a cycle.

Approach

Use DSU (union–find) with path compression and union by size. For each edge (u, v): if find(u) == find(v), u and v are already connected, so this edge forms a cycle. Otherwise union them. A DFS that ignores the edge back to its parent works too. The DSU version needs no recursion and handles disconnected graphs naturally.

Complexity: O((n + m) · α(n)) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

vector<int> parent, sz;

int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];  // path halving
        x = parent[x];
    }
    return x;
}

bool unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return false;
    if (sz[a] < sz[b]) swap(a, b);
    parent[b] = a;
    sz[a] += sz[b];
    return true;
}

int main() {
    int n, m;
    cin >> n >> m;
    parent.resize(n + 1);
    sz.assign(n + 1, 1);
    iota(parent.begin(), parent.end(), 0);
    bool cycle = false;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        if (!unite(u, v)) cycle = true;
    }
    cout << (cycle ? "YES" : "NO") << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
parent = list(range(n + 1))
size = [1] * (n + 1)


def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]  # path halving
        x = parent[x]
    return x


cycle = False
for i in range(m):
    a, b = find(data[2 + 2 * i]), find(data[3 + 2 * i])
    if a == b:
        cycle = True
        break
    if size[a] < size[b]:
        a, b = b, a
    parent[b] = a
    size[a] += size[b]
print("YES" if cycle else "NO")

Java solution

import java.util.*;

public class Main {
    static int[] parent, sz;

    static int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];  // path halving
            x = parent[x];
        }
        return x;
    }

    static boolean unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) { int t = a; a = b; b = t; }
        parent[b] = a;
        sz[a] += sz[b];
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        parent = new int[n + 1];
        sz = new int[n + 1];
        for (int i = 0; i <= n; i++) { parent[i] = i; sz[i] = 1; }
        boolean cycle = false;
        for (int i = 0; i < m; i++)
            if (!unite(sc.nextInt(), sc.nextInt())) cycle = true;
        System.out.println(cycle ? "YES" : "NO");
    }
}

Solve Detect Cycle in an Undirected Graph online · All practice problems