How do we detect cycles in an undirected graph?

The task involves determining if an undirected graph, where nodes represent cells and edges represent adjacent cells with the same color, contains any cycles.

Run dfs / bfs, if an edge leads you to a visited node, then there must be a cycle.

from collections import deque

def is_valid_cell(x, y, n, m):
    return 0 <= x < n and 0 <= y < m

def has_cycle(grid, n, m):
    # directions to move in the grid
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    # visited set to track visited cells
    visited = set()

    # perform bfs from each cell
    for i in range(n):
        for j in range(m):
            if (i, j) in visited:
                continue

            color = grid[i][j]
            q = deque([(i, j, None)])

            while q:
                x, y, prev = q.popleft()
                if (x, y) in visited:
                    # cycle found
                    return True

                visited.add((x, y))

                for k in range(4):
                    nx, ny = x + dx[k], y + dy[k]

                    if not is_valid_cell(nx, ny, n, m) or grid[nx][ny] != color:
                        continue

                    if (nx, ny) != prev:
                        q.append((nx, ny, (x, y)))

    # no cycle found
    return False

# read input
n, m = map(int, input().split())
grid = [input() for _ in range(n)]

# check if there is a cycle
if has_cycle(grid, n, m):
    print("Yes")
else:
    print("No")

def is_valid(x, y, n, m):
    return x >= 0 and x < n and y >= 0 and y < m

def has_cycle(grid):
    visited = set()

    # direction vectors for neighbors
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if (i, j) not in visited:
                stack = [(i, j, None)]

                while stack:
                    x, y, parent = stack.pop()

                    visited.add((x, y))

                    for k in range(4):
                        nx, ny = x + dx[k], y + dy[k]

                        if is_valid(nx, ny, len(grid), len(grid[0])) and grid[nx][ny] == grid[x][y]:
                            if (nx, ny) not in visited:
                                stack.append((nx, ny, (x, y)))
                            elif (nx, ny) != parent:
                                return True

    return False

# read input
n, m = map(int, input().split())
grid = [input() for _ in range(n)]

# check if there is a cycle
if has_cycle(grid):
    print("Yes")
else:
    print("No")