04084: 拓扑排序

http://cs101.openjudge.cn/dsapre/04084/

给出一个图的结构，输出其拓扑排序序列，要求在同等条件下，编号小的顶点在前。

输入

若干行整数，第一行有2个数，分别为顶点数v和弧数a，接下来有a行，每一行有2个数，分别是该条弧所关联的两个顶点编号。 v<=100, a<=500

输出

若干个空格隔开的顶点构成的序列(用小写字母)。

样例输入

样例输出

v1 v3 v2 v6 v4 v5

可能有孤立点。可能两个点之间可以有多条弧，用dic构造的图，同学入度-1能AC。

python

import heapq

def topological_sort(vertices, edges):
    # Initialize in-degree and connection matrix
    in_edges = [0] * (vertices + 1)
    connect = [[0] * (vertices + 1) for _ in range(vertices + 1)]

    # Populate the in-degree and connection matrix
    for u, v in edges:
        in_edges[v] += 1
        connect[u][v] += 1

    # Priority queue for vertices with in-degree of 0
    queue = []
    for i in range(1, vertices + 1):
        if in_edges[i] == 0:
            heapq.heappush(queue, i)

    # List to store the topological order
    order = []

    # Processing vertices
    while queue:
        u = heapq.heappop(queue)
        order.append(u)
        for v in range(1, vertices + 1):
            if connect[u][v] > 0:
                in_edges[v] -= connect[u][v]
                if in_edges[v] == 0:
                    heapq.heappush(queue, v)

    if len(order) == vertices:
        return order
    else:
        return None

# Read input
vertices, num_edges = map(int, input().split())
edges = []
for _ in range(num_edges):
    u, v = map(int, input().split())
    edges.append((u, v))

# Perform topological sort
order = topological_sort(vertices, edges)

# Output result
if order:
    for i, vertex in enumerate(order):
        if i < len(order) - 1:
            print(f"v{vertex}", end=" ")
        else:
            print(f"v{vertex}")
else:
    print("No topological order exists due to a cycle in the graph.")

python

#23n2300011075(才疏学浅)
v,a=map(int,input().split())
node=["v"+str(i) for i in range(v+1)]
dic1={i:0 for i in node}
dic2={i:[] for i in node}
for _ in range(a):
    f,t=map(int,input().split())
    dic1[node[t]]+=1
    dic2[node[f]].append(node[t])
vis=set()
cnt=0
ans=[]
while cnt<v:
    for i in range(1,v+1):
        if dic1[node[i]]==0 and node[i] not in vis:
            vis.add(node[i])
            ans.append(node[i])
            cnt+=1
            for nodes in dic2[node[i]]:
                dic1[nodes]-=1
            break
print(*ans)

04084: 拓扑排序 ​

04084: 拓扑排序