Problem statement

https://binarysearch.com/problems/Forest-Detection/

Solution

Use union find to check if we have loops.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class DSU:
    def __init__(self, N):
        self.p = list(range(N))

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr

class Solution:
    def solve(self, edges):
        n = max(max(y for _, y in edges + [[0, 0]]), max(x for x, _ in edges + [[0, 0]])) + 1
        dsu = DSU(n)
        for x, y in edges:
            if dsu.find(x) == dsu.find(y): return False
            dsu.union(x, y)
        return True