P1357 食物链(一)

这是一道算法题，题目描述如下：

在一条食物链中，有N种生物，编号为1~N。第i种生物的食物级别为Si，如果Si=1，那么它是草，其他情况下，它的食物级别比它低1，即Si-1。每种生物都有一个独一无二的捕食对象，如果生物A捕食生物B，那么生物A的食物级别一定比生物B高1，则Si > Sj。现在，给出M个生物之间的捕食关系，请你判断其中是否存在矛盾。

这题需要使用拓扑排序来解决，将食物链中生物的关系看作一张有向图，每个生物看做一个节点，如果A捕食B，则从节点A向B连一条有向边，这样就形成了一张有向图。如果图中存在环，则说明存在矛盾，否则就没有矛盾。

具体实现过程是，先统计每个节点的入度，即它前面有多少个节点，然后将所有入度为0的节点加入队列中，从队列中取出一个节点，将它指向的节点的入度减1，如果减为0，则将这个节点加入队列中。重复以上过程，直到队列为空。如果此时还有节点的入度不为0，则说明存在环，否则就没有矛盾。

代码实现如下（以C++为例）：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 5005;

int n, m;
int indeg[MAXN]; // 入度
vector<int> adj[MAXN]; // 邻接表

bool topsort() {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            indeg[v]--;
            if (indeg[v] == 0) {
                q.push(v);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (indeg[i] != 0) {
            return false;
        }
    }
    return true;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        indeg[v]++;
    }
    if (topsort()) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}