第一周萌新赛补题总结–F题-闯关游戏前言这题在赛时也算是很有灵感的一题了由于没怎么学过算法竟然连拓扑排序都不知道害反正现在也算是学会用了吧只能说棋差一招啊思路这个题其实也就是一个模板题了就跟我们学习数据结构的拓扑排序一样入度为0优先走然后走的这个还牵扯着其他数那么我们就优先队列来表示字典序小的并且还可以走的数字in数组来表示入度的量如果一个数的入度是0也就是说in[i]0那么就表示它可以走那么我们就把他放进优先队列里面然后优先队列里面的数再一个一个放进一个数组里面最后我们统计数组的大小如果数组大小不是n那就不是一个通路所以就输出NO。题目来源思路其实已经很清楚了代码如下#includebits/stdc.husingnamespacestd;#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0)#defineendl\n#defineintlonglong#definepiipairint,int#definefifirst#definesesecond#defineYEScoutYesendl;#defineNOcoutNoendl;voidsolve(){intn,m;cinnm;vectorvectorinta(n1);vectorintin(n1,0);for(inti1;im;i){intu,v;cinuv;a[u].push_back(v);in[v];}priority_queueint,vectorint,greaterintq;for(inti1;in;i){if(in[i]0)q.push(i);}vectorintarr;while(!q.empty()){autoxq.top();q.pop();arr.push_back(x);for(autot:a[x]){in[t]--;if(in[t]0)q.push(t);}}if(arr.size()!n)NOelse{YESfor(autox:arr)coutx ;coutendl;}// coutfixedsetprecision(x)}signedmain(){IOS;int_1;cin_;while(_--)solve();return0;}结语呃呃小友是一位出入茅庐的手子如感觉有繁琐可以自行增添其实就是一个拓扑排序的应用板子希望对你有用