太平阳建设集团网站购物网站首页模板下载

有向无环图是拓扑排序 

拓扑排序将图中所有的顶点排成一个线性序列，使得所有的有向边均从序列的前面指向后面。

拓扑排序使用深度优先搜索来实现，图中有环则无法进行拓扑排序

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

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

算法思路:首先记录各个点的入度

然后将入度为0的点放入队列，将队列里的点依次出对，然后删除这个点出发的边，删掉这个边同时边的另一侧的入度-1

如果所有的点都进过队列，则可以进行拓扑排序，否则输出-1，代表不能进行拓扑排序

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 100010;

vector<int> g[N];  // 邻接表存储图
int in_degree[N];  // 记录每个点的入度
int n, m;  // n 个点，m 条边

bool topological_sort() {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (in_degree[i] == 0) {
            q.push(i);  // 将所有入度为 0 的点加入队列
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";  // 输出拓扑排序的顺序
        for (auto v : g[u]) {
            in_degree[v]--;  // 删除边 (u, v)
            if (in_degree[v] == 0) {
                q.push(v);  // 如果节点 v 的入度变为 0，则加入队列
            }
        }
    }

    // 如果所有点都被访问过，说明是有向无环图，返回 true
    for (int i = 1; i <= n; i++) {
        if (in_degree[i] != 0) {
            return false;
        }
    }
    return true;
}

int main() {
    cin >> n >> m;  // 输入点的个数和边的个数
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);  // 添加边 (a, b)
        in_degree[b]++;  // b 的入度加 1
    }

    if (topological_sort()) {
        cout << "拓扑排序结果：";
    } else {
        cout << "图中存在环！";
    }

    return 0;
}