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")

From the input we are given that the total length of our path doesn’t exceed 10^5.

How can we find the shortest path in an undirected graph.

This problem involves finding the shortest path between two points on a chess field, given a set of allowed cells. We can model the chess field as an undirected graph and use breadth-first search (BFS) to find the shortest path between the two points.

To ensure that the king only moves along the allowed cells, we can represent the allowed cells as a set and only consider a path if all of its cells are in the set of allowed cells.

By using BFS, we guarantee that we find the shortest path between the two points, as BFS explores nodes in order of their distance from the starting node. If there is no path between the two points along the allowed cells, we can detect this by the fact that the BFS algorithm does not visit the ending node.

from collections import deque

def main():
    # Input
    x0, y0, x1, y1 = map(int, input().split())
    n = int(input())
    allowed = set()
    for i in range(n):
        r, a, b = map(int, input().split())
        for i in range(a, b + 1):
            allowed.add((r, i))

    # BFS
    queue = deque([(x0, y0)])
    visited = set([(x0, y0)])
    neighbors = [[-1, 0], [0, -1], [0, 1], [1, 0],
                 [-1, 1], [1, -1], [1, 1], [-1, -1]]
    level = 0
    while queue:
        level += 1
        for _ in range(len(queue)):
            x, y = queue.popleft()
            if (x, y) == (x1, y1):
                return level - 1
            for dx, dy in neighbors:
                nx, ny = x + dx, y + dy
                if (nx, ny) in allowed and (nx, ny) not in visited:
                    visited.add((nx, ny))
                    queue.append((nx, ny))

    # No path found
    return -1

print(main())

Try to simulate the given sequence of operations and maintain the state of the heap at each step.

Think about the conditions when an insert operation is required to make the sequence consistent.

One way to approach this problem is to simulate the given sequence of operations and maintain a set of all the elements currently present in the heap. Whenever a getMin operation is encountered, we check if the minimum element is present in the set. If not, we add an insert operation to insert the minimum element. Similarly, whenever a removeMin operation is encountered, we check if the set is empty. If it is, we add an insert operation to insert any element into the heap.

If the current operation is insert x, then add element x to the heap.

If current operation is removeMin, then if heap is not empty, then simply remove minimal element, otherwise if heap is empty, add operation insert x, where x can be any number, and then apply removeMin.

If current operation is getMin x then do follows:

1.While the heap is not empty and its minimal element is less than x, apply operation removeMin.

2.Now if the heap is empty or its minimal element is not equal to x, apply operation insert x.

3.Apply operation getMin x.

import heapq
def main():
    num_operations = int(input())
    
    output = []
    heap = []
    for i in range(num_operations):
        record = list(input().split())
    
        if record[0] == 'insert':
            heapq.heappush(heap, int(record[1]))
            output.append(record)
        
        elif record[0] == 'removeMin':
            if not heap:
                output.append(['insert', '1'])
                heapq.heappush(heap, 1)
            heapq.heappop(heap)
            output.append(record)
        
        else:
            x = int(record[1])
            
            while heap and heap[0] < x:
                heapq.heappop(heap)
                output.append(['removeMin'])
            
            if not heap or heap[0] > x:
                heapq.heappush(heap, x)
                output.append(['insert',  str(x)])
            
            output.append(record)
    
    print(len(output))
    for line in output:
        print(' '.join(line))

main()