Jul 2020
1 / 2
Jul 2020
Jul 2020
elif123
Jul '20

Don’t understand why getting NZEC , this code is passing all test cases.i am using bipartite graph here.

t=int(input())
for test in range(1,t+1):
a=list(map(int,input().split()))
n=a[0]
m=a[1]

arr=[]
vis=[]
colour=[]
for i in range(0,n):
    arr.append([])
for i in range(0,n):
    vis.append(0)    
for i in range(0,n):
    colour.append(0)        
for d in range(m):
    v=list(map(int,input().split()))
    x=v[0]
    y=v[1]
    arr[x-1].append(y)
    arr[y-1].append(x)

def dfs(node,c):
    vis[node]=1
    colour[node]=c
    for child in arr[node]:
        if vis[child-1]==0:
            temp1=dfs(child-1,c^1)
            if temp1 ==False:
                return False    
        else:
            if colour[node]==colour[child-1]:
                
                return False 
    return True                   

flag=1
for i in range(0,n):
    if vis[i]==0:
        temp=dfs(i,0)
        if temp ==False:
        
            flag=0
if flag==0:
    print("Scenario #{}:".format(test))
    print("Suspicious bugs found!")
else:
    print("Scenario #{}:".format(test))
    print("No suspicious bugs found!")

  • created

    Jul '20

  • last reply

    Jul '20
  • 1

    reply

  • 548

    views

  • 2

    users

  • 1

    link

nadstratosfer
Jul '20

You’re using recursive DFS, which overflows the recursion stack. Your code gets AC with this modification:

from sys import setrecursionlimit
setrecursionlimit(10000)

I’d recommend avoiding recursion wherever possible if you want to pass time limits with Python here.

On a sidenote, your code is not pythonic and ugly stylewise. For example, arrays can be initiated faster and elegantly:

graph = [[] for _ in range(n)]
visited = [0] * n                         # only with immutable element types

Use spaces for readability and variable names that mean something (temp what? flag of what? array of what?). In interpreted languages, albeit not only, decent style translates to performance, and you’re going to need it on SPOJ. Also learn fast I/O which is especially important with graph problems.