Let's look at the degrees of each node.

To form a ring topology, each node must have a degree of $$$2$$$. For a bus topology, the starting and ending nodes must have a degree of $$$1$$$, while the other $$$n - 2$$$ nodes will have a degree of $$$2$$$. In a star topology, one node must have a degree of $$$n - 1$$$, while the other $$$n - 1$$$ nodes will only have a degree of $$$1$$$. If the graph doesn't satisfy one of the above conditions, it is an unknown topology.

n,k = list(map(int,input().split()))
degree = [0 for i in range(n)]
for i in range(k):
    x,y = list(map(int,input().split()))
    x -= 1
    y -= 1
    
    #increase the degrees of both nodes
    degree[x] += 1
    degree[y] += 1

#count the occurrences of the degrees   
count = Counter(degree)

if count[2] == n:
    print('ring topology')
elif count[1] == 2 and count[2] == (n - 2):
    print('bus topology')
elif count[1] == n - 1 and count[n - 1] == 1:
    print('star topology')
else:
    print("unknown topology")

We know that node $$$1$$$ is the root, hence it always won’t have any ancestor. All other nodes might have sometimes not fixed ancestors, but we know for sure, for beginning, node 1 won’t have any unfixed ancestor (because it won’t have any). So, for beginning we can start with node $$$1$$$. More, suppose node $$$1$$$ is unfixed. The only way to fix it is to make an operation on it. Since it’s unfixed and this is the only way to fix it, you’ll be obligated to do this operation. This means, in an optimal sequence of operations, you’ll be obligated to do this operation, too.

Generally, suppose all ancestors of node $$$x$$$ are fixed. We get the current value of node $$$x$$$ after the operations done on ancestors of $$$x$$$. If the current value is not the expected one, we’ll have to do an operation on node $$$x$$$ (this is the only way to fix the node $$$x$$$). Now, after node $$$x$$$ is fixed, we can process sons of it. This strategy guarantees minimal number of operations, because we do an operation only when we’re forced to do it.

How to get $$$O(N)$$$? Suppose we are at node $$$x$$$ and want to know its current value after operations done for its ancestors. Obviously, it is defined by initial value. If we know number of operations done so far by even levels for its ancestors, number of operations done so far by odd levels and current level, we can determine the current value. Suppose these values are (initial_value, odd_times, even_times, level). We observe that $$$2$$$ operations cancel each other, so we can take this number modulo $$$2$$$. If level % 2 = 0, then only even_times will matter, and current_value = (initial_value + even_times) % 2. Otherwise, current_value = (initial_value + odd_times) % 2.

import sys
from collections import defaultdict
n = int(sys.stdin.readline().strip())
graph = defaultdict(list)

for i in range(n - 1):
    u, v = map(int, sys.stdin.readline().strip().split())
    graph[u].append(v)
    graph[v].append(u)
init = list(map(int, sys.stdin.readline().strip().split()))
goal = list(map(int, sys.stdin.readline().strip().split()))
stack = [(1, 1, 0, 0, 0)]
ans = []

while stack:
    node, par, level, even_op, odd_op = stack.pop()
    if level % 2 == 0:
        if even_op % 2:
            if 1 - init[node - 1] != goal[node - 1]:
                ans.append(node)
                even_op = 1 -even_op
        else:
            if init[node - 1] != goal[node - 1]:
                ans.append(node)
                even_op = 1 -even_op
    else:
        if odd_op % 2:
            if 1 - init[node - 1] != goal[node - 1]:
                ans.append(node)
                odd_op = 1 -odd_op
        else:
            if init[node - 1] != goal[node - 1]:
                ans.append(node)
                odd_op = 1 -odd_op
    for el in graph[node]:
        if el != par:
            stack.append((el, node, level + 1, even_op, odd_op))
print(len(ans))
for a in ans:
    print(a)

Replace the empty cells with walls if they are adjacent to bad cells

Take the escape $$$(n,m)$$$ as the source node to perform depth-first-search (DFS) traversal.

Here’s the step-by-step process:

1. Represent the graph in a grid as a graph representation.
2. Identify all the good, bad, and empty cells.
3. Replace the empty cells with walls if they are adjacent to bad cells.
4. Initialize a visited set to track visited nodes.
5. Take the cell $$$(n,m)$$$ as a source node and perform a depth-first search (DFS) traversal.
6. Once the traversal is finished, check if all good cells exist in the visited set and none of the bad cells exist in the visited set.
7. If some (one or more) good cells do not exist in the visited set, it means we can’t traverse to all the good cells, and all of the good people can’t escape.
8. If some (one or more) bad cells exist in the visited set, it means we can’t block all bad cells, and they can escape.

Time Complexity: $$$O(N * M)$$$, where $$$N$$$ is the number of rows and $$$M$$$ is the number of columns in the maze.

Space Complexity: $$$O(N * M)$$$

def inBound(row, col, n, m, visited, graph):
    return 0 <= row < n and 0 <= col < m and (row, col) not in visited and graph[row][col] != '#'

def main():
     for _ in range(int(input())):
        n, m = map(int, input().split())
        graph = []

        for _ in range(n):
            graph.append(list(input()))
        
        direc = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        good, bad, empty = [], [], []

        # Find the good, bad and empty cells
        for row in range(n):
            for col in range(m):
                if graph[row][col] == 'G':
                    good.append((row, col))
                elif graph[row][col] == 'B':
                    bad.append((row, col))
                elif graph[row][col] == '.':
                    empty.append((row, col))

        # Replace the empty cells with walls if they are adjacent to bad cells
        for row, col in empty:
            for i, j in direc:
                _row, _col = row + i, col + j
                if 0 <= _row < n and 0 <= _col < m and graph[_row][_col] == 'B':
                    graph[row][col] = '#'
                    break 

        # Check if the good cells are reachable and the bad cells are not reachable
        stack = [(n - 1, m - 1)]
        visited = set()
        while stack:
            row, col = stack.pop()
            if not inBound(row, col, n, m, visited, graph):
                continue
            visited.add((row, col))
            for i, j in direc:
                _row, _col = row + i, col + j
                stack.append((_row, _col))

        ans = 'Yes'
        for cell in good:
            if cell not in visited:
                ans = 'No'
                break
        
        for cell in bad:
            if cell in visited:
                ans = 'No'
                break

        print(ans)

if __name__ == '__main__':
    main()

To begin with, let's understand why the string will return to its original form. In fact, the graph that the permutation sets consists of simple cycles and it turns out that after a certain number of operations, each character will return to its place.

Consider each cycle as a string that is cyclically shifted every turn. It may seem that the answer is — lcm (the smallest common multiple) of the cycle lengths, but to become equal to the initial string, it is not necessary to go through the entire cycle. We can calculate the length of the minimum suitable shift $$$k_j$$$ in $$$O(len)$$$ using built in function. Note that after $$$k_j$$$ operations, the cycle will return to its original form and this will happen again after $$$k_j$$$.

operations.

The answer will be lcm of all $$$k_j$$$, since each cycle individually comes to its original form after the number of operations is a multiple of its $$$k_j$$$.

import sys
from math import gcd
 
def solve():
	# Read input for the number of elements, string, and array of integers
	n = int(sys.stdin.readline().strip())
	s = sys.stdin.readline().strip()
	a = list(map(int, sys.stdin.readline().split()))
 
	lcm = 1
	vis = [0] * n
	for i in range(n):
    	if vis[i]:
        	continue
    	cur = []
    	ind = i
    	# Traverse the cycle starting from current index
    	while not vis[ind]:
        	cur.append(s[ind])
        	vis[ind] = 1
        		ind = a[ind] - 1
    	# Create a search string by repeating current cycle twice
    	search = "".join(cur + cur)
    	# Remove the first character (repetition), if we dont remove it the answer will always be 0
    	search = search[1:]  
    	# Find the starting index of the cycle
    	index = search.find("".join(cur)) + 1  
    	lcm = (lcm* index) // gcd(lcm, index)
	return lcm
 
if __name__ == "__main__":
 
	t = int(sys.stdin.readline().strip())
	for _ in range(t):
    	# Call solve() for each test case and print the result
    	result = solve()
    	print(result)