🔥前言
本专栏收录的均为牛客网的算法题目，内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目，也有大厂的面试真题，面试、找工作完全可以来这里找机会。此外，网站内的编码主题多样化，调试功能可运用性强，可谓是非常注重用户体验。这么好的免费刷题网站还不快入手吗，快去注册开启算法百炼成神之路吧！
1、AB13 【模板】拓扑排序
学会使用邻接表解决图论问题，巧妙利用vector容器
题目链接：拓朴排序
1.1、解题思路
解决拓扑排序之前要先认识什么是拓扑排序：
对一个有向无环图(Directed Acyclic Graph简称DAG)图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
解决步骤：
使用邻接表将顶点联系起来，辅助数组inDegree表示每个顶点的入度。
借助队列和计数器变量来判断该有向图是否有环：
将入度为零的顶点入队(也就是拓扑图第一个顶点)
取队首，遍历与之相邻的顶点，若该顶点入度减一后为零就将其入队
只要队列非空就循环操作，计算器循环加一，与顶点数比较是否相等
本题末尾也不能输出空格，因此输出拓扑序列时要加限制条件
1.2、代码实现与注释
本题源码：
#include<iostream> #include<vector> #include<queue> #define M 200001 using namespace std; int main() { int n, m; cin >> n >> m; vector<int> adjList[M]; // 模拟邻接表 int inDegree[M] = { 0 };// 记录每个顶点的入度 int a, b; for (int i = 0; i < m; i++) { cin >> a >> b; adjList[a].push_back(b); inDegree[b]++; } queue<int> que; // 将初始入度为零的顶点入队 for (int i = 1; i <= n; i++) { if (inDegree[i] == 0) que.push(i); } int cnt = 0; // 用来计数，判断改图是否有环 vector<int> res; // 用来输出顶点序列 while (!que.empty()) { int u = que.front(); que.pop(); res.push_back(u); for (int i = 0; i < adjList[u].size(); i++) { // 遍历u的相邻顶点 int v = adjList[u][i]; if (--inDegree[v] == 0) que.push(v); } cnt++; } // 若计数器与顶点数相同则图无环，存在拓扑排序 if (cnt == n) { for (int i = 0; i < res.size(); i++) { cout << res[i]; // 限制输出空格的条件 if (i != res.size() - 1) { cout << " "; } } } else { cout << -1; } return 0; }
重要注释：
adjList数组是vector类型的，用来模拟邻接表
使用每个元素为一个数组的vector容器模拟邻接表进行建图
vector[a]所对应的数组中存储着该顶点所指向的其他顶点
inDegree数组代表每一个顶点的入度情况
使用一个队列，初始时将所有入度为0的顶点全部入队，之后采用BFS的思想：
依次取出队头元素并存入结果数组中，然后在邻接表中遍历该队头元素所指向的其他顶点
将这些顶点的入度全部减一，若减一后某顶点的入度变为0，则将该顶点进行入队操作，
重复此步骤直至队列为空为止。
设置一个用于判断图中是否存在环（是否可以得到拓扑序列）的计数器，在弹出队头元素后要将计数器加一，最后队列为空后，若计数器的值与顶点数相同，则说明图不存在环，可以得到拓扑序列。
