HDU-4857-逃生-反向拓扑排序+优先队列-白红宇的个人博客

HDU-4857-逃生-反向拓扑排序+优先队列

发布日期：2021-08-16 13:27:23 浏览次数：45 分类：技术文章

本文共 1077 字，大约阅读时间需要 3 分钟。

题意就是做一个符合条件的排序，用到拓扑序列。

我一开始wa了多发，才发现有几个样例过不了，发现1->2->3...的顺序无法保证。

后来就想用并查集强连，还是wa；

后来发现发用反向拓扑排序+优先队列才可以通过；

这里注意把入度为0的入队改成了出度为0的入队

下面是AC代码：

#include 
     
      #include
      
       #include 
       
        using namespace std;vector
        
         to[30000+10];int n,m,cnt;int outdeed[30000+10],topo [30000+10];void init(){    memset(outdeed,0,sizeof(outdeed));    for(int i=1;i<=n;i++)        to[i].clear();    memset(topo,0,sizeof(topo));}void toposort(){    priority_queue
         
          q;    for(int i=1;i<=n;i++)        if(!outdeed[i])q.push(i);    cnt=0;    while(!q.empty())    {        int tmp = q.top();        q.pop();        topo[++cnt]=tmp;        int k = to[tmp].size();        for(int i=0;i
          
           =1;i--) printf("%d%c",topo[i],i==1?'\n':' ');}int main(){ int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); init(); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); to[v].push_back(u); outdeed[u]++; } toposort(); output(); } return 0;}

转载于:https://www.cnblogs.com/ckxkexing/p/8419277.html

转载地址：https://blog.csdn.net/weixin_30807779/article/details/98152559 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Aspx根据模版动态创建html页

下一篇：html表单元素

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章