当前位置: 代码迷 >> 综合 >> HDU - 1285 确定比赛名次(拓扑序列)
  详细解决方案

HDU - 1285 确定比赛名次(拓扑序列)

热度:8   发布时间:2023-12-08 08:17:51.0

#include <bits/stdc++.h>using namespace std;const int N=510;
int h[N],e[N],ne[N],in[N],idx;//in数组是存储每个数的入度
int n,m;void init()//初始化
{memset(h,-1,sizeof h);idx=0;
}void add(int a,int b)//链式向前星存图
{e[idx]=b,ne[idx]=h[a],h[a]=idx++,in[b]++;
}void topsort()
{priority_queue<int,vector<int>,greater<int> > q;//优先队列vector<int> res;//res向量保存最后结果for(int i=1;i<=n;i++)//起初,入度为0的数推入队列中{if(in[i]==0){q.push(i);}}while(q.size()){int t=q.top();res.push_back(t);q.pop();//入度为0的数弹出队列for(int i=h[t];i!=-1;i=ne[i]){in[e[i]]--;//那么就会导致被弹出的数所连接的数的入度减1if(in[e[i]]==0)//如果入度为0,那么就推入队列中{q.push(e[i]);}}}for(int i=0;i<n-1;i++){cout << res[i] << " ";}cout << res[n-1] << endl;
}
int main()
{while(cin >> n >> m){init();for(int i=1;i<=m;i++){int a,b;cin >> a >> b;add(a,b);}topsort();}return 0;
}