首页 > 代码库 > 拓扑排序
拓扑排序
将DAG图转化为顺序排列的形式
可应用于DP求最长路、基于两两优劣关系求排名等题型。
前向星版代码：
#include <iostream>#include <queue>#include <cstdio>#include <vector>#define N 505using namespace std;int n,m,sum,cnt,flag;int deg[N];int head[N];struct Node{ int v,next;};struct cmp{ bool operator()(int a,int b) { return a>b; }};Node edge[N<<1];void print(int num){ if(flag==0) printf("%d",num),flag=1; else printf(" %d",num);}void topoSort(int n){ priority_queue<int,vector<int>,cmp> q; for(int i=1;i<=n;i++) if(deg[i]==0) q.push(i),deg[i]--; while(!q.empty()) { int u=q.top(); q.pop(),print(u); sum--; for(int i=head[u];i!=-1;i=edge[i].next) { Node e=edge[i]; deg[e.v]--; } for(int i=1;i<=n;i++) if(deg[i]==0) q.push(i),deg[i]--; }}void ini(){ for(int i=1;i<=n;i++) deg[i]=0,head[i]=-1,flag=0; cnt=0,sum=n;}void add(int u,int v){ deg[v]++; edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++;}int main(int argc, const char * argv[]) { while(scanf("%d%d",&n,&m)!=EOF) { int a,b; ini(); for(int i=0;i<m;i++) scanf("%d%d",&a,&b),add(a,b); topoSort(n); puts(""); } return 0;}
邻接表版代码：
#include <iostream>#include <queue>#include <cstdio>#include <vector>#define N 505using namespace std;int n,m,sum,cnt,flag;int deg[N];vector<int> g[N];struct cmp{ bool operator()(int a,int b) { return a>b; }};void print(int num){ if(flag==0) printf("%d",num),flag=1; else printf(" %d",num);}void topoSort(int n){ priority_queue<int,vector<int>,cmp> q; for(int i=1;i<=n;i++) if(deg[i]==0) q.push(i),deg[i]--; while(!q.empty()) { //if(q.size()>1) 可用于判断是否充分排序。 //如果有多个入度为0的同时入队，说明他们之间没有明确的排序条件。 int u=q.top(); q.pop(),print(u); sum--;//可用于判断是否有冲突，如果有冲突，就会导致两者或者已上的节点入度无法降为0 for(int i=0;i<g[u].size();i++) { int e=g[u][i]; deg[e]--; } for(int i=1;i<=n;i++) if(deg[i]==0) q.push(i),deg[i]--; }}void ini(){ for(int i=0;i<=n;i++) deg[i]=0,flag=0,g[i].clear(); cnt=0,sum=n;}void add(int u,int v){ deg[v]++; g[u].push_back(v);}int main(int argc, const char * argv[]) { while(scanf("%d%d",&n,&m)!=EOF) { int a,b; ini(); for(int i=0;i<m;i++) scanf("%d%d",&a,&b),add(a,b); topoSort(n); puts(""); } return 0;}
拓扑排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。