大输入导致拓扑排序崩溃

Question

你知道吗问题：你知道吗

现在你可以在伯兰州立大学学习在线课程了！Polycarp需要通过其专业的主要在线课程才能获得文凭。总共有n个课程可供通过。你知道吗

这种情况由于在线课程的依赖性而变得复杂，对于每门课程，都有一个列表，列出了在开始这门在线课程之前必须通过的课程（列表可以为空，这意味着没有限制）。你知道吗

帮助Polycarp通过最少的课程获得专业（即通过所有主要和必要的课程）。写一个程序来打印课程顺序。你知道吗

Polycarp始终如一地通过课程，上一门课程结束后，他开始下一门课程。每门课不能超过一次。你知道吗

你知道吗输入：-你知道吗

第一行包含n和k（1 ≤ k ≤ n ≤ 105）-Polycarp专业的在线课程数和主要课程数。你知道吗

第二行包含从1到n的k个不同整数-Polycarp专业主要在线课程的编号。你知道吗

接下来是n行，每行描述下一个课程：第i行对应课程i。每行从整数ti开始（0 ≤ ti ≤ n - 1）-第i行所依赖的课程数。然后是从1到n的ti个不同整数的序列-按随机顺序排列的课程数，第i个取决于此。任何课程都不能自力更生。你知道吗

保证所有值ti之和不超过10^5。你知道吗

你知道吗输出：-你知道吗

如果不可能，-1

如果可能的话，然后打印出他需要修的课程数，然后是他修课程的顺序

代码评论：-你知道吗

import sys
flag=True
sys.setrecursionlimit(2000000)
c=[];st=[];
def topo(s):#Traversing the array and storing the vertices
    global c,st,flag;
    c[s]=1; #Being Visited
    for i in adjli[s]:#visiting neighbors
        if c[i]==0:
            topo(i)
        if c[i]==1:
            flag=False# If Back Edge , Then Not Possible
    st.append(str(s))
    c[s]=2 # Visited

try:
    n,k=map(int,input().split(' '))#Number Of Courses,Dependencies
    main=list(map(int,input().split(' ')))#Main Dependencies
    depen=[]#Dependencies List
    for i in range(n):
        depen.append(list(map(int,input().split(' ')))[1:]);c.append(0)#Append Input To Dependencies List, Marking Visited as 0(False)
    c.append(0)
    adjli=[]
    adjli.append(main)#Assuming Main Course at index 0 with dependencies as Main Dependency(main)
    for i in range(len(depen)):
        adjli.append(depen[i])#Appending Other Dependencies
    topo(0)#TopoLogical Sort Order
    st.pop(-1)#popping the assumed Main Couse
    if flag:# IF possible then print
        print(len(st))
        print(' '.join(st))
    else:
        print(-1)
except Exception as e:
    print(e,"error")

我做了什么？你知道吗

我做了拓扑排序并存储了遍历顺序。我假设专业课程存储在索引0中，并相应地形成了图。如果遇到后缘，我返回-1。你知道吗

有什么问题吗？你知道吗

代码为小输入提供了正确的输出，但在大输入的情况下遇到了运行时错误例如：你知道吗

要生成的代码输入：-你知道吗

print(100000,1)
print(100000)
for i in range(100000):
  if i==0:
    print(i)
  else:
    print(1,i)

我做了什么来解决这个问题？你知道吗

我试图打印运行时错误，但没有显示任何内容。你知道吗

链接到问题：-Question

我的解决方案：-Solution

Answer 1

这是递归过程中堆栈的问题。Python有一个低递归限制问题，即使您显式地声明了这个限制。这个问题在codeforces博客中提到：https://codeforces.com/blog/entry/45135/

一种解决方案是使用迭代方法而不是递归方法来实现函数拓扑。你知道吗

更改的代码可以是：

import sys
flag=True
sys.setrecursionlimit(2000000000)
c=[];st=[];
cur_adj=[]
def topo(s):#Traversing the array and storing the vertices
    global c,st,flag;
    stack = [s]
    while(stack):
        s = stack[-1]
        c[s]=1; #Being Visited
        if(cur_adj[s] < len(adjli[s])):
            cur = adjli[s][cur_adj[s]]
            if(c[cur]==0):
                stack.append(cur)
            if(c[cur]==1):
                flag=False# If Back Edge , Then Not Possible
            cur_adj[s]+=1
        else:
            c[s]=2
            st.append(str(s))
            del stack[-1]

try:
    n,k=map(int,input().split(' '))
    main=list(map(int,input().split(' ')))
    depen=[]
    for i in range(n):
        depen.append(list(map(int,input().split(' ')))[1:]);c.append(0)
        cur_adj.append(0)
    c.append(0)
    cur_adj.append(0)
    adjli=[]
    adjli.append(main)#Assuming Main Course at index 0 with dependencies as Main Dependency(main)
    for i in range(len(depen)):
        adjli.append(depen[i])#Appending Other Dependencies
    topo(0)#TopoLogical Sort Order
    st.pop(-1)#popping the assumed Main Couse
    if flag:# IF possible then print
        print(len(st))
        print(' '.join(st))
    else:
        print(-1)
except Exception as e:
    print(e,"error")

这段代码实现了堆栈在递归期间所做的事情。curïu adj是一个列表，curïu adj[i]保存i的相邻节点的索引以访问下一个节点。一旦访问了所有i的相邻节点，i就会从堆栈中弹出（堆栈是一个普通的列表，它模仿递归堆栈）。你知道吗