给定一个图，判断是否能连成环，若可以则输出 N O NO NO，否则输出 Y E S YES YES。我用了 b f s bfs bfs去进行拓扑。
#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <functional> #include <iostream> #include <map> #include <queue> #include <stack> #include <string> #include <vector> using namespace std; typedef long long ll; const int N = 1e5 + 10, NN = 1e3 + 10, INF = 0x3f3f3f3f; const ll MOD = 1e9 + 7; int num_edge, n, m, sum; int head[N], indegree[N]; struct Edge { int next; int to; } edge[N]; void add_edge(int from, int to) { num_edge++; edge[num_edge].next = head[from]; edge[num_edge].to = to; head[from] = num_edge; } void topo() { priority_queue<int, vector<int>, greater<int> > q; for (int i = 0; i < n; i++) { if (!indegree[i]) { q.push(i); ++sum; } } while (!q.empty()) { int u = q.top(); q.pop(); for (int i = head[u]; i != -1; i = edge[i].next) { --indegree[edge[i].to]; if (!indegree[edge[i].to]) { q.push(edge[i].to); ++sum; } } } if (sum == n) printf("YES\n"); else printf("NO\n"); } void init() { num_edge = 0; sum = 0; memset(head, -1, sizeof head); memset(indegree, 0, sizeof indegree); } int main() { while (scanf("%d%d", &n, &m) && n) { init(); for (int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); indegree[v]++; add_edge(u, v); } topo(); } }