完善程序题 1

图是否存在有向环，若有拓扑排序输出拓扑排序，并输出 “不存在有向环”，否则直接输出“存在有向环”。

输入：

第一行两个正整数 n，m 表示节点数和边数。

接下来 m 行，每行 2 个整数 x,y 表示节点 x->y 有一条边。

输出：

一个拓扑排序：按拓扑排序输出点的编号。若拓扑排序不唯一，输出任意一个均可，并输出“不存在有向环”。若无拓扑排序，直接输出“存在有向环”

1. 填空(1) 处应填（ ）{{ select(1) }}

• !cnt[i]
• cnt[i]
• cnt[i]=0
• cnt[i]==1

2. 填空(2) 处应填（ ）{{ select(2) }}

• q.push(v)
• q.pop()
• cnt[u]--
• cnt[v]--

3. 填空(4) 处应填（ ）{{ select(3) }}

• q.pop()
• q.push(v)
• tpc--
• tpc++

4. 填空(4) 处应填（ ）{{ select(4) }}

• tpc!=n
• tpc==n
• tpc==0
• tpc!=0

5. 填空(5) 处应填（ ）{{ select(5) }}

• cnt[x]++
• G[y].push(x)
• cnt[y]++
• G[y].push_back(x)

完善程序题 2

狄克斯特拉算法算法是由荷兰计算机科学家狄克斯特拉于 1959 年提出的。这个算法是计算从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。算法的主要特点是以起点为中心向外层层扩展，知道扩展到终点为止。

6. 填空（1）处应填{{ select(6) }}

• infinity
• dis[j]
• 0
• 1

7. 填空（2）处应填{{ select(7) }}

• infinity
• dis[j]
• 0
• 1

8. 填空（3）处应填{{ select(8) }}

• quanzhi
• 0
• infinity
• 1

9. 填空（4）处应填{{ select(9) }}

• j
• dis[j]
• flag[j]
• i

10. 填空（10）处应填{{ select(10) }}

• dis[u]
• edg[u][v]
• dis[u]+edg[u][v]
• infinity