拓扑排序 （有向无环图）
概念：
拓扑排序
AOV网
实现
代码实现B3644 【模板】拓扑排序 / 家谱树 - 洛谷
#include<iostream>
#include<vector>
#include<queue>
using namespace std;const int N = 110;
vector<int> edge[N];//把后代进行拖尾
int in[N];//记录自己的前辈有多少个int main()
{int n; cin >> n;for (int i = 1; i <= n; i++){int j;while (cin >> j, j){edge[i].push_back(j);//把后代接在后面in[j]++;//后代的前辈+1}}queue<int> q;for (int i = 1; i <= n; i++)//把没有前辈的加进队列{if (in[i] == 0)q.push(i);}while (q.size()){auto x = q.front(); q.pop();cout << x << " ";for (auto s : edge[x])//前辈没了，该前辈的后代的前辈-1{in[s]--;if (in[s] == 0)q.push(s);//后代变成0，加进队列}}return 0;
}P2712 摄像头 - 洛谷
#include<iostream>
#include<vector>
#include<queue>
using namespace std;const int N = 510;//摄像头位置可以到500
vector<int> edge[N];//记录后面的
int in[N];//标记前面的
bool st[N];//标记要砸坏的摄像头int main()
{int n; cin >> n;for (int i = 1; i <= n; i++){int x, y;cin >> x >> y;//位置 可以看多少个st[x] = true;//标记for (int i = 1; i <= y; i++){int ch; cin >> ch;edge[x].push_back(ch);in[ch]++;}}//进队列queue<int> q;for (int i = 0; i <= 500; i++){if (st[i] && in[i] == 0)q.push(i);}while (q.size()){int x = q.front(); q.pop();for (auto& ch : edge[x]){in[ch]--;if (in[ch] == 0)q.push(ch);}}int ret = 0;for (int i = 0; i <= 500; i++){if (st[i] && in[i] != 0)ret++;}if (ret == 0)cout << "YES" << endl;else cout << ret << endl;
}
加了一个标记要砸坏的bool st[]
进队列：是餐厅里的摄像头，并且没有前辈
记录ret:是餐厅里的摄像头，in不为0
P4017 最大食物链计数 - 洛谷
//路径类dp动态规划 + 拓扑排序填表
#include<iostream>
#include<queue>
#include<vector>
using namespace std;const int N = 5010;
const int MOD = 80112002;int n, m;
vector<int> edge[N];//记录拖尾
int in[N];//记录前驱
int out[N];//找最大捕食者
int f[N];//从起点到i位置的路径条数，处理不同块之间的情况int main()
{cin >> n >> m;for (int i = 1; i <= m; i++){int x, y; cin >> x >> y;edge[x].push_back(y);//记录后者in[y]++; out[x]++;//后者的前辈+1，前者的后背+1}queue<int> q;//进队列for (int i = 1; i <= n; i++){if (in[i] == 0)//没有前者就给我进队列{f[i] = 1;//第一只的f[i]进行初始化为1q.push(i);}}while (q.size()){int x = q.front(); q.pop();for (auto& ch : edge[x])//遍历后辈{f[ch] =(f[ch] + f[x])%MOD;//当前的+前辈的in[ch]--;//前辈--if (in[ch] == 0)q.push(ch);//为0 干进队列}}int ret = 0;//怎么找最大捕食者？找出度为0的数字for (int i = 1; i <= n; i++){if (out[i] == 0)ret = (ret+f[i])%MOD;}cout << ret << endl;return 0;
}P1113 杂务 - 洛谷
拿最大的进行更新，因为大的做完了，小的也就做完了。
最短时间，所有情况下，取最大值。
#include<iostream>
#include<vector>
#include<queue>
using namespace std;const int N = 1e4 + 10;
vector<int> edge[N];//记录拖尾
int f[N];//记录到i下标的最小值
int in[N];//记录前面有几个
int len[N];//记录工作完需要的时间int n;
int main()
{cin >> n;for (int i = 1; i <= n; i++){int x, a; cin >> x >> len[i];while (cin >> a, a){edge[x].push_back(a);in[a]++;}}//进队列queue<int> q;for (int i = 1; i <= n; i++){if (in[i] == 0)q.push(i);}int ret = 0;while (q.size()){int x = q.front(); q.pop();f[x] += len[x];ret = max(ret, f[x]);for (auto& ch : edge[x]){f[ch] = max(f[ch], f[x]);//一个一个遍历更新出最大的。具体还是看解题思路吧in[ch]--;if (in[ch] == 0)q.push(ch);}}cout << ret << endl;return 0;
}