1 / 3
Jul 2020

your code goes here

from sys import stdin, stdout

t = int(input())

for z in range(t):
n, m = map(int, stdin.readline().split())

adj_list = {}
visited = [0] * (n + 1)
colour_of_node = [0] * (n + 1)

def dfs_iterative(node, color):
    stack = []
    stack.append(node)
    visited[node] = 1
    colour_of_node[node] = color

    while len(stack) > 0:
        root = stack.pop()
        for i in adj_list[root]:
            if visited[i] == 0:
                stack.append(i)
                colour_of_node[i] = colour_of_node[root] ^ 1
                visited[i] = 1
            else:
                if colour_of_node[root] == colour_of_node[i]:
                    return False
    return True

for _ in range(m):
    u, v = map(int, stdin.readline().split())

    if u in adj_list:
        adj_list[u].append(v)
    if v in adj_list:
        adj_list[v].append(u)
    if u not in adj_list:
        adj_list[u] = [v]
    if v not in adj_list:
        adj_list[v] = [u]

# checking if the graph is bipartite for all the connected components
for i in range(1, n + 1):
    if visited[i] == 0:
        ans = dfs_iterative(i, 0)
        if ans == False:
            break

# print(visited)
# print(colour_of_node)

print("Scenario #" + str(z + 1) + ":")
if ans:
    print("No suspicious bugs found!")
else:
    print("Suspicious bugs found!")
  • created

    Jul '20
  • last reply

    Jul '20
  • 2

    replies

  • 605

    views

  • 2

    users

  • 1

    like

  • 1

    link

This is a case that gives runtime error. It should allow you to figure out where it’s happening.

1
5 2
1 2
3 4

BUGLIFE1

Thank you so much @simes I totally forgot that while adding nodes and their edges to the adjacency list I did not add nodes with no edges. I got accepted in one go just by adding one line tysm :slight_smile: