2026联赛1 拓扑排序

F-闯关游戏_河南萌新联赛2026第一场河南工业大学F-闯关游戏涉及 优先队列小根堆拓扑排序拓扑排序是数据结构刚学的算法 这个题也算是一个模板题就是去找那个顶点的度为0 然后去把它删了 循环再去找直到所有顶点都遍历过解题思路拓扑排序判断是否成环路 成环说明关卡无法通关1.记录路线 用邻接表或者数组 存2.记录每个顶点的度3.找度为04.删除度为0的边 5.输出//F #includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second using namespace std; ​ int main() { IOS ll t; cint; while(t--) { ll n,m; cinnm; vectorvectorlladj(n1); vectorllind(n1,0); for (int i1;im;i) { ll u,v; cinuv; adj[u].push_back(v);//记录线路 ind[v];//记录每个顶点的度 } priority_queuell,vectorll,greaterll q; //题目中要求按字典序最小输出使用优先队列 最小堆 for(int i1;in;i) { if(ind[i]0) { q.push(i);//用队列来遍历度为0的边 } } ll cnt0;//用来记录删去点的请况以观察是否成环 vectorllans;//可以先存一下出顶点结果 while(!q.empty()) { ll xq.top(); q.pop(); ans.push_back(x); cnt; for(auto it:adj[x]) { ind[it]--;//删去边之后的顶点度更新 if(ind[it]0) { q.push(it);//查看度更新后出现度为0的情况 } } } if(cnt!n)//当不相等时就是有环存在 { coutNoendl; } else { coutYesendl; for(int k0;kans.size();k) { coutans[k] ; } coutendl; } ​ } ​ // coutfixedsetprecision(x) ; return 0; }