图论——拓扑排序

拓扑排序的步骤：

• 计算每个点的入度。

• 入度为 0 就加入队列。

• 当队列不为空则循环：

  • 取出队首元素并输出。

  • 遍历队首元素的连边，对应节点的入度 −1。

  • 当对应的节点入度为 0 就加入队列。

#include<iostream> #include<vector> #include<algorithm> #include<queue> using namespace std; int n; //节点数量 vector <int> g[110]; vector <int> in(110, 0);//入度 queue <int> q;//用于BFS遍历入度为0的节点 vector <int> ans;//存储拓扑排序结果 int main() { cin >> n; //建图 for (int i = 1;i <= n;i++) { int x = 1; while (x != 0) { cin >> x; if (x != 0) { g[i].push_back(x); in[x]++; } } } //把入度为0的点加入队列 for (int i = 1;i <= n;i++) { if (in[i] == 0) q.push(i); } // 当队列不为空时继续 while (!q.empty()) { int t = q.front(); // 获取队列头部元素 ans.push_back(t); // 将t加入拓扑排序结果 q.pop(); // 从队列中移除t // 处理t的所有后继节点 for (int e : g[t]) { // 消除边(t,e)对入度的影响，e的入度减1 in[e]--; //把入度为0的点加入队列 if (in[e] == 0) q.push(e); } } for (int e : ans) cout << e << " "; return 0; }