题解 | #星际航线规划#

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

using namespace std;

bool topologicalSort(int n, const vector<vector<int>>& adj,
                     vector<int>& visited) {
    vector<int> inDegree(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int j : adj[i]) {
            inDegree[j]++;
        }
    }

    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    int count = 0;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        visited[node] = 1;
        count++;
        for (int next : adj[node]) {
            if (--inDegree[next] == 0) {
                q.push(next);
            }
        }
    }

    return count == n; // 如果访问的节点数等于总节点数，则无环
}

void dfs(int node, const vector<vector<int>>& adj, vector<int>& visited) {
    visited[node] = 1;
    for (int next : adj[node]) {
        if (!visited[next]) {
            dfs(next, adj, visited);
        }
    }
}

bool canVisitAllNodes(int n, const vector<vector<int>>& adj) {
    vector<int> visited(n + 1, 0);
    if (!topologicalSort(n, adj, visited)) {
        return false; // 存在环
    }

    // 检查是否所有节点都被访问过
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            return false;
        }
    }

    return true;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
    }

    if (canVisitAllNodes(n, adj)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}
// 64 位输出请用 printf("%lld")