acgo题库
  • 首页
  • 题库
  • 学习
  • 竞赛
  • 讨论
  • 排行
  • 团队
  • 备赛专区

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
登录
注册
题目详情提交记录(0)
  • 手搓

    userId_undefined

    Srobot

    时间刺客空间掌握者时空双修者枚举·枚举小能手秩序白银模拟·模拟练习生
    4阅读
    0回复
    2点赞
  • #题解

    拓扑排序(字典序最小)题解 题目描述 给定一个n个顶点m条边的有向图,输出字典序最小的拓扑排序。若图中存在环,则输出"has circle."。 输入格式 * 第一行两个整数n,m * 接下来m行,每行两个整数u,v表示有向边 输出格式 * 若无环,输出拓扑排序结果 * 有环则输出"has circle." 算法思路 1. Kahn算法:基于BFS的拓扑排序算法 2. 优先队列:使用小根堆保证每次取出当前可访问的最小顶点 3. 环检测:若最终排序结果顶点数≠n,说明存在环 代码实现 复杂度分析 时间复杂度:O(n log n + m) 优先队列操作O(log n) 每个顶点和边各处理一次 空间复杂度:O(n + m)

    userId_undefined

    91VIP

    时间刺客时空双修者空间掌握者倔强青铜
    23阅读
    0回复
    0点赞
  • tj

    #include <bits/stdc++.h> using namespace std; int n,m,ind[50]; vector<int> a[50]; vector<int> res; int main(){ cin >> n >> m; for (int i=0;i<m;i++){ int u,v; cin >> u >> v; a[u].push_back(v); ind[v]; } priority_queue<int,vector<int>,greater<int> > q; for (int i=1;i<=n;i){ if (ind[i]==0) q.push(i); } while (!q.empty()){ int now = q.top(); q.pop(); res.push_back(now); for (int i=0;i<a[now].size();i++){ int next=a[now][i]; ind[next]--; if (ind[next]==0) q.push(next); } } if (res.size()!=n){ cout << "has circle."; }else{ for (int i=0;i<n;i++){ cout << res[i] << ' '; } } return 0; }

    userId_undefined

    Lexore_

    小有名气8月全勤卷王时空双修者题解仙人快乐小狗
    8阅读
    0回复
    1点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页