《课程表危机》：如何用拓扑排序检测“循环依赖”？-程序员充电站

题目背景：

小明这学期选了一堆课，但是他发现学校的选课系统有点坑。有些课程有前置要求，比如必须先修完“高等数学”，才能去修“大学物理”。

小明整理了一份课程依赖清单，但他隐约觉得这份清单有问题——如果存在 A 依赖 B，B 依赖 C，C 又依赖 A 的情况，那他就永远没法把课修完了（死循环）！

现在请你帮小明检查一下，按照这份清单，他到底能不能顺利修完所有课程？

题目描述：

学校里共有n门课程，编号从1到n。

小明拿到了m条先修规则。每一条规则描述为u v，表示课程u是课程v的先修课（即必须先修完 u，才能修v）。

请你判断是否存在“课程死锁”（即循环依赖），如果存在死锁，说明小明不能修完所有课；如果不存在死锁，说明他可以顺利修完。

输入格式：

第一行输入两个正整数n, m，分别表示课程总数和先修规则的数量。

接下来m行，每行两个整数u, v，表示课程u必须在课程v之前修完。

输出格式：

如果存在循环依赖（即无法修完），输出Yes。

如果不存在循环依赖（即可以修完），输出No。

样例输入：

4 4 1 2 2 3 3 4 1 4

样例输出：

No

样例解释：

课程依赖关系为：1->2, 2->3, 3->4, 1->4。

修课顺序可以是：1 -> 2 -> 3 -> 4。不存在环，所以输出No（代表没有死锁）。

数据范围：

2<=n<=10000

0<=m<=100000

1<=u, v<=n, u!=v

1. 背景故事：选课的烦恼

小明这学期选了一堆课，但是他发现学校的选课系统有点坑。有些课程有前置要求，比如必须先修完“高等数学”，才能去修“大学物理”。

作为计算机系的学生，我们能不能写个程序帮小明检查一下：按照这份清单，他到底能不能顺利修完所有课程？

2. 问题抽象

本质上，这是一个有向图的问题：

节点：代表每一门课程。
有向边：代表依赖关系。如果课程u是v的先修课，则存在一条边u->v。
目标：判断图中是否存在环。

如果图中存在环（例如1->2->3->1），则说明存在循环依赖，无法修完；如果是一个有向无环图，则说明存在一个合理的修课顺序（即拓扑序列）。

3. 核心算法：拓扑排序 (Kahn算法)

要解决这个问题，最经典的方法是使用Kahn算法（基于入度的拓扑排序）。

算法步骤：

统计入度：计算每一门课有多少门“直接先修课”（入度）。
入队：找到所有入度为0的课（不需要先修课，直接能上的课），放入队列。
消除：
- 从队列取出一门课（假设修完了）。
- 将这门课指向的所有后续课程的入度减1（相当于解锁了它们的一个条件）。
- 如果某门后续课程的入度变成了0，说明它的条件全满足了，将其入队。
判断：
- 如果最终入过队的课程数量等于总课程数N，说明所有课都能修完（无环）。
- 如果小于N，说明剩下的课互为前置，形成了环（有环）。

4. 代码实现

为了追求极致的运行效率，本代码采用了以下两个优化技巧，非常适合算法竞赛（ACM/OI）：

链式前向星：替代vector存图，内存占用更小，遍历速度更快。
手写队列：替代queue，减少STL的常数开销。

题目描述

输入：n (课程数), m (规则数)。接下来m行u, v，表示u是v的先修课。
输出：如果有环（无法修完），输出Yes；否则输出No。

完整代码

//有向图环判断 链式前向星+手写队列版本 #include <iostream> #include <cstring> using namespace std; int n,m; int h[10010];//邻接表头指针数组 int vtex[100010];//临接表第i条边终点下标 int nxt[100010];//与第i条边同起点的下一条边的索引 int idx;//边数 int d[10010];//存每个点的入度 int q[10010];//存入度为0的点（手写队列） void addedge(int u,int v){ vtex[idx]=v; nxt[idx]=h[u]; h[u]=idx++; } void tuopu(){ int rear=0; int front=1; //先把一开始入度为0的点（无需先修课）都存入队列q for(int i=1;i<=n;i++) if(d[i]==0) q[++rear]=i; while(front<=rear){//front=rear+1代表队列为空 int x=q[front];//访问队首元素 front++;//队首元素出队 //接下来把所有从x出发的边都删掉 然后这些边所指向的点的入度都减1 //x是p的先修课 int p=h[x]; while(p!=-1){//访问x所有邻接点 d[vtex[p]]--;//因为删除了和邻接点之间的边，所以入度都要减1 //如果邻接点入度变为0，就入队 if(d[vtex[p]]==0) q[++rear]=vtex[p]; p=nxt[p];//更新指针 } } if(rear==n) cout<<"No";//如果所有点都入队了，代表没有环 else cout<<"Yes";//否则就是有环 } int main() { cin>>n>>m; //初始化头指针数组为空 memset(h,-1,sizeof(h)); //邻接表存图 for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; addedge(u,v); d[v]++;//v点入度+1 } //拓扑排序 tuopu(); return 0; }