Day10-A4 DAG与拓扑排序专项（GESP七八级风格）

参考GESP高等级对技能依赖DAG、图性质与遍历程序的考法。程序判断输入有向图是否为DAG。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main(){
    int n,m;cin>>n>>m;
    vector<vector<int>> g(n+1); vector<int> in(n+1,0);
    while(m--){int u,v;cin>>u>>v;g[u].push_back(v);++in[v];}
    queue<int> q;
    for(int i=1;i<=n;++i) if(in[i]==0) q.push(i);
    int cnt=0;
    while(!q.empty()){
        int u=q.front();q.pop();++cnt;
        for(int v:g[u]) if(--in[v]==0) q.push(v);
    }
    cout<<(cnt==n?"DAG":"CYCLE");
}

第 1 题

有向无环图的英文缩写是（ ）。

{{ select(1) }}

• LAN
• DAG
• DNS
• DFS

第 2 题

拓扑序要求边 $u\to v$ 满足（ ）。

{{ select(2) }}

• v在u之前
• u与v必须相邻输出
• u在v之前
• u和v编号连续

第 3 题

Kahn算法首先把哪些顶点加入队列？（ ）

{{ select(3) }}

• 所有孤立边
• 出度为0的顶点
• 度数最大的顶点
• 入度为0的顶点

第 4 题

一个DAG的拓扑序（ ）。

{{ select(4) }}

• 一定不存在
• 只由边数决定
• 一定唯一
• 可能不唯一

第 5 题

输入 4 3，边为 1 2、2 3、1 4，程序输出（ ）。

{{ select(5) }}

• 3
• 4
• DAG
• CYCLE

第 6 题

若增加边 3 1，程序输出（ ）。

{{ select(6) }}

• CYCLE
• DAG
• 0
• 无法编译

第 7 题

执行 --in[v] 的含义是（ ）。

{{ select(7) }}

• 增加v的一条入边
• 移除已处理前驱对v的依赖影响
• 删除顶点v
• 计算最短距离

第 8 题

最终 cnt<n 说明（ ）。

{{ select(8) }}

• 存在有向环
• 图一定弱连通
• 图没有边
• 拓扑序唯一