)
简介
本篇介绍两道有关拓扑排序的问题，难度为洛谷黄题
前置知识
拓扑排序就是一系列有不同优先级的事件的排列，其中优先级相同的事情可以相互交换
关键结论一个图能进行拓扑排序的充要条件是它是一个有向无环图(DAG)
入度和出度的概念
1.入度：以v为终点的边的数量，称为v的入度
2.出度：以v为起点的边的数量，称为v的出度
入度出度与优先级的关系假如一个点的入度为0，说明它的优先级最高，假如一个点的出度等于0，说明它的优先级最低
第一篇题解
模板题
题目描述
- B3644拓扑排序
B3644 【模板】拓扑排序 / 家谱树
题目描述
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列，使得每个人的后辈都比那个人后列出。
输入格式
第1 11行一个整数N NN（1 ≤ N ≤ 100 1 \le N \le 1001≤N≤100），表示家族的人数。接下来N NN行，第i ii行描述第i ii个人的后代编号a i , j a_{i,j}ai,j，表示a i , j a_{i,j}ai,j是i ii的后代。每行最后是0 00表示描述完毕。
输出格式
输出一个序列，使得每个人的后辈都比那个人后列出。如果有多种不同的序列，输出任意一种即可。
输入输出样例 #1
输入 #1
5 0 4 5 1 0 1 0 5 3 0 3 0输出 #1
2 4 5 3 1思路分析
模板题目就简单讲一下代码实现思路，先统计每一个点的入度，统计完所有点后，将入度为0的点放入队列当中，接着从这几个点向外延申，把延申到的点的入度减1，因为对于延申到的点来说，前面的点已经被删除掉了，如果入度减少到0，放入队列当中即可。
代码展示
#include<iostream>#include<algorithm>#include<queue>#include<vector>usingnamespacestd;constintN=110;vector<int>ans;vector<int>node[N];queue<int>q;intn;intin[N];voidbfs(){while(!q.empty()){intt=q.front();q.pop();for(autox:node[t]){in[x]--;if(in[x]==0){ans.push_back(x);q.push(x);}}}}intmain(){cin>>n;for(inti=1;i<=n;i++){intx;while(cin>>x&&x){node[i].push_back(x);in[x]++;}}for(inti=1;i<=n;i++)if(in[i]==0){q.push(i);ans.push_back(i);}bfs();for(inti=0;i<ans.size();i++)cout<<ans[i]<<" ";return0;}细节分析
注意一下这个题目的输出顺序，前辈在前后辈在后，入度为0的点(前辈)是先被放入ans当中的，所以这道题顺序输出即可，有些题目可能是倒序输出的，后面讲的这中类型我们往往会采用栈这个结构存储答案，因为最后直接弹出即可，当然用vector存储也是可以的，倒序输出即可。
AI注释代码
#include<iostream>#include<algorithm>#include<queue>#include<vector>usingnamespacestd;constintN=110;// 节点数量的最大限制vector<int>ans;// 存储拓扑排序的结果vector<int>node[N];// 邻接表：node[t] 存储节点t指向的所有邻接节点queue<int>q;// 拓扑排序用的队列，存储入度为0的节点intn;// 总节点数intin[N];// 入度数组：in[x] 表示节点x的入度（有多少节点指向x）// 拓扑排序核心：Kahn算法（基于入度+队列）voidbfs(){// 队列非空时，持续处理入度为0的节点while(!q.empty()){intt=q.front();// 取出队首的入度为0节点q.pop();// 遍历当前节点t的所有邻接节点xfor(autox:node[t]){in[x]--;// 销毁t后，x的入度减1（t不再指向x）// 若x的入度变为0，说明x无前置依赖，可加入拓扑序列和队列if(in[x]==0){ans.push_back(x);q.push(x);}}}}intmain(){cin>>n;// 输入节点总数// 输入每个节点的邻接关系（构建有向图）for(inti=1;i<=n;i++){intx;// 循环输入节点i的邻接节点，输入0时终止while(cin>>x&&x){node[i].push_back(x);// 构建边：i → xin[x]++;// 节点x的入度+1（因为i指向x）}}// 初始化队列：将所有入度为0的节点加入队列（无前置依赖，可优先处理）for(inti=1;i<=n;i++)if(in[i]==0){q.push(i);ans.push_back(i);// 入度为0的节点直接加入拓扑结果}// 执行拓扑排序的BFSbfs();// 输出拓扑排序结果for(inti=0;i<ans.size();i++)cout<<ans[i]<<" ";return0;}第二篇题解
- P2712摄像头
题目描述
P2712 摄像头
题目描述
食品店里有n nn个摄像头，这种摄像头很笨拙，只能拍摄到固定位置。现有一群胆大妄为的松鼠想要抢劫食品店，为了不让摄像头拍下他们犯罪的证据，他们抢劫前的第一件事就是砸毁这些摄像头。
为了便于砸毁摄像头，松鼠歹徒们把所有摄像头和摄像头能监视到的地方统一编号，一个摄像头能被砸毁的条件是该摄像头所在位置不被其他摄像头监视。
现在你的任务是帮松鼠们计算是否可以砸掉所有摄像头，如不能则输出还没砸掉的摄像头的数量。
输入格式
第1 11行，一个整数n nn，表示摄像头的个数。
第2 22到n + 1 n+1n+1行是摄像头的信息，包括：摄像头的位置x xx，以及这个摄像头可以监视到的位置数m mm，之后m mm个数y yy是此摄像头可以监视到的位置（砸了这些摄像头之后自然这些位置就监视不到了）。
输出格式
若可以砸掉所有摄像头则输出“YES \texttt{YES}YES”，否则输出还没砸掉的摄像头的数量（不带引号）。
输入输出样例 #1
输入 #1
5 1 1 2 2 1 1 3 1 7 4 1 1 5 0输出 #1
2说明/提示
1 ≤ n ≤ 100 1 \leq n \leq 1001≤n≤100。
0 ≤ m ≤ 100 0 \leq m \leq 1000≤m≤100。
0 ≤ x , y ≤ 500 0 \leq x,y \leq 5000≤x,y≤500。
思路分析
这道题就是拓扑排序的问题，当摄像头a能拍到摄像头b时，你要拆掉b，你首先得拆掉a，这就是做事情的顺序，题目要求我们在不被摄像头拍到的情况下能拆掉多少个摄像头，也就是说，我们根据这些摄像头的拓扑排序，能拆掉几个摄像头，其中的拓扑约束在题目中的表述是谁能监视到哪个位置，如果a能监视到b，说明a有一条指向b的边
这道题为什么会问我们是否能拆掉所有摄像头呢，此时我们就要回归一个图有拓扑排序的充要条件了，从样例数据中我们可以发现，这个图是存在环的，有环这个图就没有完整的拓扑排序了，只有部分，我们要求的就是这个部分的拓扑序有几个元素，然后做差即可。注意，无论是自环还是和其他点一起构成的环都是无法排到拓扑序当中的，自己可以模拟一下就知道了。
几个坑点
1.这个描述的不清不楚的输入我真服了，以1 1 2为例子，描述的是在1这个位置有一个摄像头，它能看到一个位置，这个位置是2。
2.有些看到的位置它可能并没有摄像头，比如3 1 7这个数据，在位置3有一个摄像头有，能看到一个位置，这个位置是7，但是整组数据里7这个位置并没有摄像头，所以我们在读入的时候还要有一个st数组判该点有无摄像头
代码展示
#include<iostream>#include<algorithm>#include<queue>#include<vector>#include<cstring>usingnamespacestd;constintN=510;intn,cnt;vector<int>branch[N];queue<int>q;boolst[N];intin[N];voidbfs(){while(!q.empty()){autot=q.front();q.pop();for(autox:branch[t]){in[x]--;if(st[x]&&in[x]==0){cout<<x<<"*"<<endl;cnt++;q.push(x);}}}}intmain(){cin>>n;for(inti=1;i<=n;i++){intnum,m,x;cin>>num>>m;st[num]=true;for(inti=1;i<=m;i++){cin>>x;branch[num].push_back(x);in[x]++;}}for(inti=0;i<=N;i++)if(st[i]&&in[i]==0){cnt++;q.push(i);}bfs();if(n-cnt==0)cout<<"YES"<<endl;elsecout<<n-cnt<<endl;return0;}细节分析
建议大家都用第一种写法，第二种很危险
AI注释代码
#include<iostream>#include<algorithm>#include<queue>#include<vector>#include<cstring>usingnamespacestd;constintN=510;// 节点（摄像头位置）的最大编号限制intn,cnt;// n：摄像头总数；cnt：成功销毁的摄像头数量vector<int>branch[N];// 邻接表：branch[t]存储摄像头t监视的所有位置queue<int>q;// 拓扑排序队列，存储可销毁的摄像头（入度为0）boolst[N];// st[i]=true 表示i是摄像头的位置intin[N];// 入度数组：in[x]表示位置x被多少个摄像头监视// 拓扑排序（Kahn算法）：销毁可移除的摄像头，更新依赖voidbfs(){// 队列非空时，持续处理可销毁的摄像头while(!q.empty()){autot=q.front();// 取出队首可销毁的摄像头位置q.pop();// 遍历当前摄像头t监视的所有位置xfor(autox:branch[t]){in[x]--;// 销毁t后，x被监视的次数减1（入度-1）// 若x是摄像头位置 且 入度为0（无其他摄像头监视），则x可销毁if(st[x]&&in[x]==0){cout<<x<<"*"<<endl;// 调试输出：标记可销毁的摄像头xcnt++;// 销毁数+1q.push(x);// x入队，后续处理其监视的位置}}}}intmain(){cin>>n;// 输入摄像头总数// 输入每个摄像头的信息：位置num + 监视位置数m + 监视的位置列表for(inti=1;i<=n;i++){intnum,m,x;cin>>num>>m;// num：摄像头位置；m：该摄像头监视的位置数量st[num]=true;// 标记num是摄像头位置// 读取m个被监视的位置，构建邻接表+更新入度for(inti=1;i<=m;i++){cin>>x;branch[num].push_back(x);// 摄像头num监视位置xin[x]++;// 位置x的入度+1（被num监视）}}// 初始化队列：找出所有「是摄像头+入度为0」的位置（初始可销毁）for(inti=0;i<=N;i++)if(st[i]&&in[i]==0){cnt++;// 初始销毁数+1q.push(i);// 入队等待处理}bfs();// 执行拓扑排序，销毁所有可销毁的摄像头// 输出结果：全部销毁则输出YES，否则输出未销毁的数量if(n-cnt==0)cout<<"YES"<<endl;elsecout<<n-cnt<<endl;return0;}一点延申：我们如何输出字典序最小的拓扑序呢
将队列改为优先队列即可，因为本人比较懒所以注释都是ai加的
#include<iostream>#include<vector>#include<queue>usingnamespacestd;constintN=1e5+10;vector<int>g[N];// 邻接表intind[N];// 入度数组intmain(){intn,m;cin>>n>>m;// 读入m条边while(m--){inta,b;cin>>a>>b;g[a].push_back(b);ind[b]++;// b的入度+1}// 最小堆（优先队列），保证字典序最小priority_queue<int,vector<int>,greater<int>>pq;// 入度为0的节点入队for(inti=1;i<=n;i++){if(ind[i]==0)pq.push(i);}vector<int>ans;// 存储拓扑序列while(!pq.empty()){intu=pq.top();pq.pop();ans.push_back(u);for(intv:g[u]){ind[v]--;// 删除边 u->vif(ind[v]==0)// 入度为0则入队pq.push(v);}}// 输出结果if(ans.size()!=n){cout<<"图中存在环，无法拓扑排序\n";}else{for(intx:ans)cout<<x<<" ";cout<<endl;}return0;}
