拓扑排序（Kahn算法)

●将入度为0的点组成一-个集合S

●每次从S里面取出一个顶点u (可以随便取)放入L,然后遍历顶点u的所有边(u,v),并删除之，并判断如果该边的另一个顶点v，如果在移除这一条边后入度为0,那么就将这个顶点放入集合S中。不断地重复取出顶点然后重复这个过程…

●最后当集合为空后，就检查图中是否存在任何边。如果有，那么这个图一定有环路，否者返回L,L中顺序就是拓扑排序的结果.

然后对于拓扑排序还有DFS算法模板，参考博客

以下模板是参考该博客，留作笔记。

Kahn模板

//Kahn算法,关键在于需要维护一个入度为0的顶点的集合int n,m;int inDeg[N];  //i点的入度vector
   
    vec[N];  //i点的邻接表,即i与哪些点相连int ans[N];    //排序结果数组 int topSort()    //返回值代表是否有环,排序结果在ans数组{
       	int cnt=0;    	queue
    
     q;  //如果需要相同优先级的顶点,序号小的先输出,则可建立优先队列,即    	//priority_queue
     
      
       ,greater
       
         >q;    	while(!q.empty())        	    q.pop();    	for(int i=1;i<=n;i++)        	    if(inDeg[i]==0)            	        q.push(i);    	while(!q.empty()){
           	    int now = q.front();        	    q.pop();        	    ans[++cnt]=now;     //个数+1并存数组        	    int len = vec[now].size();        	    for(int i=0;i
        
         >n>>m; for(int i=1;i<=n;i++) vec[i].clear(); memset(inDeg,0,sizeof(inDeg)); for(int i=1;i<=m;i++){ cin>>x>>y; inDeg[y]++; vec[x].push_back(y); }}

DFS模板

//dfs实现,从出度的角度来构造,递归到最后返回int n,m;vector
   
    vec[N];  //i点的邻接表,即i与哪些点相连int ans[N],cnt;    //排序结果数组,cnt记录个数int parent[N]; //记录其前置节点//int d[N], Time, f[N]; //可以不要,时间time初始化为0，d[]记录第一次被发现时，f[]记录结束检查时int vis[N]; //标记数组vis[i]=0表示还未访问过点i,c[i]=1表示已经访问过点i，//并且还递归访问过它的所有子孙，c[i]=-1表示正在访问中，尚未返回 bool dfs(int s) //深度优先搜索（邻接表实现），记录时间戳，寻找最短路径{
        vis[s]=-1;   //正在访问     //Time++;d[s]=Time;     int len = vec[s].size();     for(int i=0;i
    
     >x>>y;          vec[x].push_back(y);     }}

B-猫猫向前冲

众所周知， TT 是一位重度爱猫人士，他有一只神奇的魔法猫。

有一天，TT 在 B 站上观看猫猫的比赛。一共有 N 只猫猫，编号依次为1，2，3，…，N进行比赛。比赛结束后，Up 主会为所有的猫猫从前到后依次排名并发放爱吃的小鱼干。不幸的是，此时 TT 的电子设备遭到了宇宙射线的降智打击，一下子都连不上网了，自然也看不到最后的颁奖典礼。

不幸中的万幸，TT 的魔法猫将每场比赛的结果都记录了下来，现在他想编程序确定字典序最小的名次序列，请你帮帮他。

Input

输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示猫猫的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即编号为 P1 的猫猫赢了编号为 P2 的猫猫。

Output

给出一个符合要求的排名。输出时猫猫的编号之间有空格，最后一名后面没有空格!

其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。

Sample Input

4 31 22 34 3

Output

1 2 4 3

提取题目信息：N个点，M个关系，其实关系是满足传递闭包的A战胜B   B战胜C，  那么A一定可以战胜C，对于胜负关系不确定的，就采用编号从小到大排列，也就是符合拓扑排序条件，下面我用Kahn算法写的

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int maxn=1010;priority_queue
       
        
         ,greater
         
           > pQ;//小根堆 vector
          
            Q;//容器 int head[maxn],in_deg[maxn],tot,N,M,p1,p2;//N为点数，M为边数 struct edge{ int to,next,w;};edge e[maxn*2];void Init(){ //初始化 for(int i=0;i
           
            >p1>>p2; add_edge(p1,p2,1); } toposort(); } return 0;}

转载地址：http://ddwzi.baihongyu.com/

你可能感兴趣的文章

目录

拓扑排序（Kahn算法)

B-猫猫向前冲