数学（三）

一个有向无环图，如果图中有入度为 0 的点，就把这个点删掉，同时也删掉这个点所连的边。

一直进行上面出处理，如果所有点都能被删掉，则这个图可以进行拓扑排序。

典型代表：食物链

参考代码如下

include：＜bits/stdc++.h＞

using namespace std;

const int N = 100010;

int n, m;

int h[N], e[N], ne[N], idx;//存图

int in[N]; // 存储每个结点的入度

void add(int a, int b)

{

e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;

}

bool topsort() {

vector＜int＞ L;

queue＜int＞ S;

for (int i = 1; i ＜= n; i++) {//遍历一遍顶点的入度。

if (!in[i]) S.push(i);

}//如果入度为 0, 则可以入队列

while (!S.empty()) { //循环处理队列中入度为0的点

int u = ont();

S.pop();

L.push_back(u);

for (int i = h[u]; i != -1; i = ne[i]) //循环删除 u 发出的边

{

int j = e[i];//a 有一条边指向b

if (--in[j] == 0) //删除边后，b的入度减1

S.push(j);//如果b的入度减为 0,则 b 可以输出，入队列

}

}

if (L.size() == n)//如果队列中的点的个数与图中点的个数相同，则可以进行拓扑排序

{

for (auto i: L) cout ＜＜ i ＜＜ ' ';//队列中保存了所有入度为0的点，依次输出

return true;

} else return false;

}

int main()

{

cin＞＞n＞＞m;

memset(h, -1, sizeof h);

for (int i = 1; i ＜= m; i ++ )

{

int a, b;

cin＞＞a＞＞b;

add(a, b);

in[b] ++ ;

}

if (!topsort()) puts("-1");

return 0;

}