首页 > 其他分享 >U107394 拓扑排序模板

U107394 拓扑排序模板

时间:2024-02-23 21:23:09浏览次数:41  
标签:U107394 cnt int 拓扑 Next 队列 排序 模板

原题链接

在拓扑排序的基础上加上了一个条件:尽可能按字典序排序,这就使得题目难度加大。

题解:拓扑排序+小根堆

拓扑排序是采用队列一个一个出队列来删除对应结点的边,那么我们只需要保证每次出队列的结点都尽可能小,就能保证字典序。

每次出队列的值都为队列中的最小值,刚好可以采用小根堆来实现。

code

 

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int head[N],Next[N],to[N],sum[N],cnt=1,a[N];
void build(int x,int y){
    Next[cnt]=head[x];
    to[cnt]=y;
    head[x]=cnt++;
    sum[y]++;
}
int main(){
    priority_queue<int,vector<int>,greater<int>> que;
    int n,m,cnt2=0;
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        build(x,y);
    }
    for (int i=1;i<=n;i++) if (sum[i]==0) que.push(i);
    while (!que.empty()){
        a[cnt2++]=que.top();
        int fx=que.top();
        que.pop();
        for (int j=head[fx];j>0;j=Next[j]){
            if (--sum[to[j]]==0) que.push(to[j]);
        }
    }
    for (int i=0;i<cnt2;i++)
        if (i==0) cout<<a[i];
        else cout<<" "<<a[i];
    return 0;
}

 

标签:U107394,cnt,int,拓扑,Next,队列,排序,模板
From: https://www.cnblogs.com/purple123/p/18030388

相关文章

  • poly模板
    多项式全家桶#include<bits/stdc++.h>#defineFu(i,a,b)for(registerinti=a;i<=b;i++)#defineFd(i,a,b)for(inti=a;i>=b;i--)#definemod998244353usingnamespacestd;intksm(inta,intk){ intans=1; while(k){ if(k&1)ans=1ll*ans*a%mod; ......
  • 我的模板
    StringsHashtemplate<intN>structStringHashing{chars[N];i64mod[2]={1610612741ll,805306457ll};i64pw[N][2];i64w[N][2];voidinit(intm){pw[0][0]=pw[0][1]=1;for(inti=1;i<=m;++i){pw[i][0]=......
  • 模拟退火模板
    模拟退火模板#include<bits/stdc++.h>#defineMAX_TIME0.9//时间限制(s)#defineFu(i,a,b)for(registerinti=(a);i<=(b);i++)usingnamespacestd;doubleRand(){return1.0*rand()/RAND_MAX;}intcalc(intz,ints[605],intx){//计算差值 if(ans<=)//更新按时......
  • 线段树模板
    向上回溯voidpushup(intrt){ t[rt].sum+=t[lc].sum+t[rc].sum; t[rt].mx=max(t[lc].mx,t[rc].mx);}建树voidbuild(intrt,intl,intr){ t[rt].l=l; t[rt].r=r; if(l==r){ t[rt].mx=t[rt].sum=a[l]; return; } intmid=(l+r)>>1......
  • DFS算法模板(2488:A Knight's Journey)
    DFS算法(C++版本)题目一:链接:http://bailian.openjudge.cn/practice/2488/解析思路:骑士找路就是基本的DFS,用递归不断找到合适的路,找不到就回头直到找到合适的路。该题难点:要是实现字典序,也就是同样的两种选择,要走到A1而不是B1。所以就有了{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1......
  • 回溯算法模板 & 78子集代码
     voidbacktracking(参数){   if(终止条件){       存放结果;       return;   }   for(选择:本层集合中元素(树中节点孩子的数量就是集合的大小)){       处理节点;       backtracking(路径,选择列表);//递归       ......
  • 网络最大流(模板)
    不加弧优化#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=10005;intn,m,s,t;structedge{intv,nxt,val;}e[N*2];inthead[N],cnt=1;intdis[N];intmaxflow;voidadd(intu,intv,intval){ e[++cnt].val=va......
  • 清新简蓝响应式网站模板Traveler
    清新简蓝响应式网站模板Traveler适合做个人博客自媒体类站点,可以做技术类,分享心情类文章博客,界面简洁,实用,利seo排名优化。首页采用无限加载更多文章,效果很酷。traveler模板主题在更大的程度上照顾每个人的需求,菜单、首页每个栏目、侧栏小工具都可以自主开启关闭,只需在后......
  • 模板匹配里的一些数学原理
    模板匹配里的一些数学原理我们知道,在openCV里,模板匹配中匹配度的计算公式有三类。SQDIFF、CCORR、CCOEFF。下面我们来简单介绍一下这三类计算方法,并比较其不同之处。openCV里的模板匹配SQDIFFSQDIFF全称SumofSquaredDifference(SSD),即差的平方和。其离散形式为:\[E(\v......
  • vue3项目模板:新建一个vite+vue3项目,并做基础化建设
    原文地址:https://blog.csdn.net/weixin_43239880/article/details/130355138新建一个vite+vue3项目,并做基础化建设1.使用npmcreatvite@latest新建一个vue3项目2.生成git仓库3.将prettier的规则加入到eslint中(可选操作,建议有)4.添加commitLint(可选操作,建议有)5.加入UI组件库,以ele......