Apr 2017
1 / 5
Apr 2017
Apr 2017
omiq17
Apr '17

I badly need some help. I am continuously getting Runtime Error(NZEC). I have checked with multiple test cases in my terminal and all have given right answers.
I can't find any reason why I am getting runtime error. Here is my code:

bombs, relations = map(int, input().split())
graph = [[] for i in range(bombs+1)]

for i in range(relations):
    bomb1, bomb2 = map(int, input().split())
    graph[bomb1].append(bomb2)
    
def dfs(bomb):
    count = 1
    visit[bomb] = 1
    if len(graph[bomb]) > 0:
        for i in graph[bomb]:
            if visit[i] == 0:
                count = count + dfs(i)

    return count

maxImpact = 0
for i in range(1, bombs+1):
    visit = [0 for i in range(bombs+1)]
    impact = dfs(i)
    if impact > maxImpact:
        maxImpact = impact

print(maxImpact)

Please help me. Thanks in advance.

  • created

    Apr '17

  • last reply

    Apr '17
  • 4

    replies

  • 940

    views

  • 2

    users

  • 1

    like

tjm
Apr '17

This approach most likely hits a recursion limit on larger test cases. You can try changing it with sys.setrecursionlimit, or even better just use a non-recursive approach.

omiq17
Apr '17

I think the problem has occurred because of lru_cache.
Thus, I updated my code to this...

import sys
from functools import lru_cache
sys.setrecursionlimit(10000000)


def main():
    bombs, relations = map(int, input().split())
    graph = [[] for i in range(bombs+1)]

    for i in range(relations):
        bomb1, bomb2 = map(int, input().split())
        graph[bomb1].append(bomb2)

    @lru_cache(maxsize=100000)
    def dfs(bomb):
        count = 1
        visit[bomb] = 1
        if len(graph[bomb]) > 0:
            for i in graph[bomb]:
                if visit[i] == 0:
                    count = count + dfs(i)

        return count

    maxImpact = 0
    for i in range(1, bombs+1):
        visit = [0 for i in range(bombs+1)]
        impact = dfs(i)
        if impact > maxImpact:
            maxImpact = impact

    print(maxImpact)

main()

Guess what?
Now I get Wrong Answer at test case(7)!!

tjm
Apr '17

Caching answers would be fine for acyclic graphs, but is not a valid optimization for graphs with cycles.