大输入导致拓扑排序崩溃

Question

问题：-

现在您可以在 Berland 州立大学学习在线课程了！ Polycarp 需要通过他专业的 k 个主要在线课程才能获得文凭。总共有 n 门课程可供选择。

在线课程的依赖性使情况变得复杂，每门课程都有一个列表，列出了在开始该在线课程之前必须通过的那些（列表可以为空，这意味着没有限制）。

帮助 Polycarp 通过最少数量的课程来获得专业（这意味着通过所有主要和必修课程）。编写一个打印课程顺序的程序。

Polycarp 一直通过课程，他在完成上一门课程后开始下一门课程。每门课程不能超过一次。

输入：-

第一行n和k(1 ≤⟩k ≤ n ≤ 105)——坡旅甲专业的在线课程数和主课数。

第二行包含从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 处并相应地形成了图表。如果遇到 BackEdge，我返回 -1。

有什么问题？

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

生成输入的代码：-

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

我做了什么来解决这个问题？

我尝试打印运行时错误，但没有显示任何内容。

Link 问题：-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_adj 是一个列表，其中 cur_adj[i] 保存 i 的下一个要访问的相邻节点的索引。一旦 i 的所有相邻节点都被访问过，i 就会从堆栈中弹出（堆栈是一个模仿递归堆栈的普通列表）。

大输入导致拓扑排序崩溃

Large Input Causes Topological Sort To BreakDown

python

algorithm

runtime-error

graph-theory

python-3.x