# [模板] 拓扑排序

## Kahn算法

• 将所有入度为 $0$ 的点插入队列 $S$ 中
• 当队列 $S$ 不为空的时候，去除队首 $x$，将 $x$ 插入数组 $ans$
• 删除所有从 $x$ 出发的有向边
• 检查有无新的入度为 $0$ 的点，插入队列 $S$ 中
• 回到第二步

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge
while S is non-empty do
remove a node n from S
add n to tail of L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error   (graph has at least one cycle)
else
return L   (a topologically sorted order)


## 例题 Luogu – 1038 神经网络

### 题目描述

$$C_i = \sum_{j,i \in E} W_{ji}C_j – U_i$$

### 输入样例

5 6
1 0
1 0
0 1
0 1
0 1
1 3 1
1 4 1
1 5 1
2 3 1
2 4 1
2 5 1


### 输出样例

3 1
4 1
5 1


### 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 100 + 10;
const int MAXM = 20000 + 10;

int Head[MAXN], to[MAXM], Next[MAXM], w[MAXM], tot = 1;
bool vis[MAXN], flag[MAXN];
int in[MAXN], out[MAXN], ans[MAXN], u[MAXN], cnt;

int x = 0;
int p = 1;

char ch = getchar();

while(ch < '0' || ch > '9'){
if(ch == '-')
p = 0;
ch = getchar();
}

while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}

return p ? x : (-x);
}

inline void add(int a, int b, int c){
to[tot] = b;
w[tot] = c;
}

int que[MAXN], l, r;
int n, m;

inline void toop(){
for(register int i=1; i<=n; i++){
if(!in[i]){
que[r++] = i;
vis[i] = true;
}
}

while(l != r){
int x = que[l++];

int v = to[i];

if(vis[v]){
ans[x] += ans[v] * w[i];
}else{
in[v]--;

if(in[v] == 0){
que[r++] = v;
}
}
}

if(!flag[x]){
ans[x] -= u[x];
}

ans[x] = max(ans[x], 0);
vis[x] = true;
}
}

int main(){

for(register int i=1; i<=n; i++){

if(ans[i] != 0){
flag[i] = true;
}
}

for(register int i=1; i<=m; i++){

in[b]++;
out[a]++;

}

toop();

bool flag2 = false;

for(register int i=1; i<=n; i++){
if(ans[i] > 0 && out[i] == 0){
printf("%d %d\n", i, ans[i]);
flag2 = true;
}
}

if(!flag2){
puts("NULL");
}
return 0;
}