I am using dfs to find the if the graph is bipartite or not. I am also checking whether graph is disconnected or not like a cycle of 4 vertices and cycle of 3 vertices. Also the cases like less number of interactions in which only interactions are to be considered. I have tried many test cases given in this forum but I am not able to understand where my code fails.
def bipartite(adj):
visited = [0]*len(adj)
for source in range(len(adj)):
if visited[source] == 0:
stack = [source]
grp = 1
while len(stack) != 0:
v = stack.pop()
if visited[v] == 0:
visited[v] = grp
if grp==1:
grp=2
else:
grp = 1
for u in adj[v]:
if visited[u]>0 and visited[u] == visited[v]:
return 1#not bipartite
if visited[u] == 0:
stack.append(u)
return 0#bipartite
for i in range(1,int(raw_input())+1):
p, q = map(int, raw_input().split())
adj = {}
for x in range(p): adj[x] = []
for _ in range(q):
a,b = map(int, raw_input().split())
adj[a-1].append(b-1)
adj[b-1].append(a-1)
print 'Scenario'+' #'+str(i)+':'
if bipartite(adj)==1:
print "Suspicious bugs found!"
else:
print "No suspicious bugs found!"