package org.loda.graph;import org.loda.structure.Stack; import org.loda.util.In;/*** * @ClassName: Topological * @Description: 拓扑排序是所有节点dfs的逆后序，也就是每个节点任务完成的时间的逆序排序 * @author minjun * @date 2015年5月24日 下午7:17:53 **/ public class Topological {/*** 由于拓扑排序是df获取所有节点的逆后序排序* 这里利用Stack后序存储元素，那么获取出来就是反向（逆）后序排列的拓顺序*/...
G++261ms13MB 题意：给出n门课程的修读所需要的前置课程的关系，按理说应该是个拓扑图，但是因为某些原因导致了混乱，所以有可能不是一个拓扑图。现在的问题是，判断该图是否为一个拓扑图（即无环图）。思路：每次删除全部入度为0的结点，一直删下去肯定是没有任何点存在的，如果不是拓扑图的话就必有环，那么肯定有点的入度永远不为0。若到删到最后没有点存在，那么就是correct的。 1 #include<bits/stdc++.h>2usingnamespace s...
确定比赛名次Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)Total Submission(s) : 51 Accepted Submission(s) : 32Font: Times New Roman | Verdana | GeorgiaFont Size: ← →Problem Description有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场...
Rank of TetrisTime Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 7961 Accepted Submission(s): 2266Problem Description自从Lele开发了Rating系统，他的Tetris事业更是如虎添翼，不久他遍把这个游戏推向了全球。为 了更好的符合那些爱好者的喜好，Lele又想了一个新点子：他将制作一个全球Tetris高手排行榜，定时更新，名堂要比福布斯富豪榜还响。关于如何排 名，这个...
题目链接：http://lightoj.com/volume_showproblem.php?problem=1003题意是有m个关系格式是a b；表示想要和b必须喝a，问一个人是否喝醉就看一个人是否能把所有种类的饮料喝完，能输出Yes，不能输出No；其实就是有向图判断是否存在环，可以用拓扑排序来求拓扑排序：每次找到一个入度为0的点加入队列，删除与之相连的边，循环操作，得到的序列就是拓扑序（前面的必须出现在后面的前面）； #include<stdio.h> #include<string.h> #inc...
【算法总结】图论-拓扑排序一、概念设有一个有向无环图（DAG 图），对其进行拓扑排序即求其中结点的一个拓扑序列，对于所有的有向边（U，V）（由U指向V），在该序列中结点U都排列在结点 V 之前。满足该要求的结点序列，被称为满足拓扑次序的序列。求这个序列的过程，被称为拓扑排序。 由满足拓扑次序序列的特征我们也能得出其如下特点：若结点U经过若干条有向边后能够到达结点V，则在求得的序列中U必排在V之前。 在了解了拓扑次序的...
1.1.BGP协议最佳路径选择算法BGP是一个路径矢量路由协议，也就是说，它的工作就是在自主系统间交换路由信息，以便发现访问互联网某处数据的最有效路径。每个 BGP路由器通过邻居声名与周边的一个或多个路由器连接。一旦建立了邻居关系，这些BGP路由器之间就会相互交换路由信息。据我最近一次统计，整个互联网上有大约12.5万个路由信息，因此要配备一个强大的路由器才能将所有BGP路由信息接收下来。1.1.1.BGP 最佳路径选择算法概述由...
class Graph:def__init__(self):self.V = []class Vertex:def__init__(self, x):self.key = xself.color = ‘white‘self.d = 10000self.f = 10000self.pi = Noneself.adj = []self.next = Noneclass Solution:def Dfs(self, G):for u in G.V:u.color = ‘white‘u.pi = Noneglobal timetime = 0for u in G.V:if u.color == ‘white‘:self.DfsVisit(G, u)def DfsVisit(self, G, u):global timetime = time + 1u.d = timeu.color =...
题面Problem Description 有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。Input 输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数...
http://acm.hdu.edu.cn/showproblem.php?pid=4857逃生Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 6665 Accepted Submission(s): 1950Problem Description糟糕的事情发生啦，现在大家都忙着逃命。但是逃命的通道很窄，大家只能排成一行。现在有n个人，从1标号到n。同时有一些奇怪的约束条件，每个都形如：a必须在b之前。同时，社会是不平等的，这些人有的穷有的...
对有向无边图的一种排序，它使得如果存在一条从 Vi 到 Vj 的路径，那么在排序中 Vj 出现在 Vi 后面方法：找出任意一个没有入边的顶点开始，将其及其出度边删除，重复伪码如下：void Topsort(Graph G) {Queue Q;int Count = 0;Vertex V, W;Q = CreateQueue(NumVertex);MakeEmpty(Q);for each vertex Vertexif (Indegree[V] == 0)Enqueue(V, Q)while (!Empty(Q)) {V = Dequeue(Q);TopNum[V] = ++Count;for each W adjacent to Vif (-...
Sorting It All Out poj-1094 题目大意：给出一些字符串之间的大小关系，问能否得到一个唯一的字符串序列，满足权值随下标递增。 注释：最多26个字母，均为大写。 想法：显然，很容易想到用toposort处理，对于每一个刚刚读入的大小关系，我们对进行一次拓扑排序，由于点数最多是26，所以总时间复杂度是$10^2$的。然后通过题面，可以发现第一个和第三个判定依据是可以中途退出的，而第二个条件是必须最后才...
http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1804题意：……思路：对于某条路径，在遍历到某个点的时候，之前遍历过的点都可以到达它，因此在这个时候对答案的贡献就是∑(a1 + a2 + a3 + ... + ai) * bv，其中a是之前遍历到的点，v是当前遍历的点。这样想之后就很简单了。类似于前缀和，每次遍历到一个v点，就把a[u]加给a[v]，然后像平时的拓扑排序做就行了。 1 #include <bits/stdc++.h>2usingnamespace std;3#define N ...
链接：http://poj.org/problem?id=1094题意&思路：直接拓扑排序。多解输出一串英文，有环输出一段英文，唯一解输出一段英文及排序结果。细节：题目描述不是很清楚，如果不看discuss我肯定要WA出翔。discuss里总结了两点关键的：1. 输入一条边时如果此时拓扑有解就输出这个解，即使后面的边成有向环也不管了，所以每次输入的时候都得进行拓扑排序。2. 判断存在有向环应先于判断多解。这道题主要是题目坑爹。#include<cstring> #incl...
欢迎参加——每周六晚的BestCoder（有米！）逃生Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2325 Accepted Submission(s): 655Problem Description糟糕的事情发生啦，现在大家都忙着逃命。但是逃命的通道很窄，大家只能排成一行。现在有n个人，从1标号到n。同时有一些奇怪的约束条件，每个都形如：a必须在b之前。同时，社会是不平等的，这些人有的穷有的富。1号...