蓝桥杯算法提高VIP-卡勒沃夫之弱水路三千(提高型)-题解（Python代码）

解题思路:用拓扑排序

注意事项:

参考代码:

from collections import defaultdict
class Graph:
        def __init__(self,vertices):
                self.graph=defaultdict(list)#如果字典里没有这个元素，会返回类型默认值
                self.V=vertices
        def addEdge(self,u,v):
                self.graph[u].append(v)

        def topologicalSortUtil(self,v,visited,stack):
                visited[v]=True
                for i in self.graph[v]:
                        if visited[i]==False:
                                self.topologicalSortUtil(i,visited,stack)
                stack.insert(0,v)
        def topologicalSort(self,dic):
                visited = dic.copy()
                stack=[]
                for key in dic.keys():
                        if visited[key]==False:
                                self.topologicalSortUtil(key,visited,stack)
                for i in stack:
                        print(i,end=' ')
                print()

t=int(input())
while t:
        dic={};l1=[];l2=[]
        n=int(input())
        for i in range(n):
                a,b=input().split()
                l1.append(a)
                l2.append(b)
        l=l1+l2
        se=set(l)#去重，看有多少个前女友即节点
        len1=len(se)
        g=Graph(len1)
        for i in zip(l1,l2):#利用zip()函数返回的元组列表传参
                g.addEdge(i[0],i[1])
        for i in se:
                dic.update({i:False})#初始化节点
        g.topologicalSort(dic)
        t-=1