距离蓝桥杯52天
学习算法的目的是为了提升我们的编码能力
付出总有回报 不付出一定没有回报
了解拓扑排序之前，先了解AOV网：
在有向图中若以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为AOV网
比如C1指向C4，说明C4活动的开展以C1的开展为前提（C1没完成就不能去弄C4）
知道了AOV网图，就可以引入拓扑序列的概念：
拓扑序列：拓扑序列是顶点活动网(AOV网）中将活动按发生的先后次序进行的一种排列
这么说有点抽象，传送门：某站上视频对这个讲解的很好
值得一提的是：任何一个有向无环图一定有拓扑序列，因此拓扑序列可以用来检测环
拓扑排序之前，先了解有向图的三个基本概念：入度，出度，度
入度：指向该顶点的入边 出度：从该顶点指出的边 度：入度和出度的总和（与顶点相关联的边的条数）
从图上来看，拓扑排序需要这么做（视频里也有详细的分析过程，建议去看，强烈建议）：
那么对于代码来说，我们需要运用深搜的思想来执行拓扑排序的操作，1：找到图中入度为0的顶点 压栈 2：处于栈顶的顶点出栈 并加入列表（另外创建的存储结构，用于存储拓扑序列中的元素） 访问该顶点的所有邻居，如果其存在入度为0的邻居，压栈，执行操作2，如果不存在，回溯。
下面以上图为例，将C1，C2...C7依次对应为字母abcdefg，给出创建拓扑序列的代码：
#准备工作上需要一个字典:用于存放连接关系 def topsort(graph): #初始化所有点的入度为0 indegrees=dict((i,0) for i in graph.keys()) #传入入度大小 for i in graph.keys(): for j in graph[i]: indegrees[j]+=1#'a':'cd'，代表a指向c和d,那么c和d的入度增加1 #获取入度为0的顶点 stack=[i for i in indegrees.keys() if indegrees[i]==0] #创建拓扑序列 seq=[] while stack:#深搜 tmp=stack.pop()#出栈 seq.append(tmp)#加入拓扑序列 for k in graph[tmp]:#遍历邻居,邻居入度-1，邻居入度为0入栈 indegrees[k]-=1 if indegrees[k]==0: stack.append(k) if len(seq)==len(graph): print(seq)#输出拓扑序列 else: print('存在环')#当存在环，最终余下的点入度都不为0，Seq个数少于总顶点数 G={ 'a':'cd', 'b':'df', 'c':'e', 'd':'efg', 'e':'g', 'f':'g', 'g':'' } topsort(G) #['b', 'a', 'd', 'f', 'c', 'e', 'g']
第一次没优化只有71分，优化了第二次是85。（这最后一个如有大佬知道怎么过的请教一下）
代码设计思路：找能够组成圈的所有点，根据这些点找到最大环。
首先解决如何计算圈的大小问题：比如A结点经过一系列结点最后回到了A结点，我们要知道圈的大小，只需要知道这一过程中A走过了几个不同的结点，换句话说，这个圈内有几个元素（集合的思想)。然后比较各个圈的大小即可知道最大环。
这里有一点需要强调：虽然我们可以通过遍历每个点（能够组成圈的点），枚举出所有圈大小的情况，但是会有重复，当数据大起来，就会超时（71）。那怎么样才能避免重复呢，思考，比如题目给出的实例，2，3，4，5组成一个圈，假设我在遍历结点2的时候，计算出了这个圈的大小是4，那么圈内的结点，在下一次访问都不需要再访问了，也就是说下一次可以直接访问结点6。
原因：问题就在于圈内的结点有没有可能与其他结点组成更大的圈，如果我们不再访问，会不会导致范围缩小或者遗漏？答案是不会的。因为，如果要组成更大的圈，圈内的结点必然要与圈外的结点连接。由于圈内的结点是作为圈的一部分，那么必定已经有一条边指向这个结点。如果存在这个结点与圈外的结点构成更大的圈，那么必然与圈外的结点有连接，那么这个结点就会同时指向两个结点，就不符合题意了。
#准备工作上需要一个字典:用于存放连接关系 def topsort(graph): #初始化所有点的入度为0 indegrees=dict((i,0) for i in graph.keys()) #传入入度大小 for i in graph.keys(): indegrees[graph[i]]+=1 #获取入度为0的顶点 stack=[i for i in indegrees.keys() if indegrees[i]==0] #创建拓扑序列 seq=[] while stack:#深搜 tmp=stack.pop()#出栈 seq.append(tmp)#加入拓扑序列 for k in graph[tmp]:#遍历邻居,邻居入度-1，邻居入度为0入栈 indegrees[k]-=1 if indegrees[k]==0: stack.append(k) if len(seq)==len(graph): print(seq)#对于本题而言一定有圈 else: ans=0#最大圈的大小 res=[i for i in indegrees if indegrees[i]!=0]#环上的点 found=[]#用于减少次数：已查找过的点 for j in res:#寻找最大环 if j not in found: start=j p=set() while G[j]!=start: found.append(j) p.update([int(j)]) j=G[j] found.append(j) p.update([int(j)]) ans=max(ans,len(p)) print(ans) n=int(input().strip()) m=list(map(int,input().strip().split())) G={} for i in enumerate(m): G[str(i[0]+1)]=str(i[1]) topsort(G)
我是小郑 正在奔赴热爱奔赴山海！
