HDU3342 - Legal or not?
这是一道关于拓扑排序的题目
#include <iostream> #include <vector> #include <queue> #include <cstring> using namespace std; const int MAX = 100; vector<int> graph[MAX]; int inDegree[MAX]; bool TopologicalSort(int n) { queue<int> q; int count = 0; for (int i = 0; i < n; ++i) { if (inDegree[i] == 0) q.push(i); // 把所有入度为0的node放到queue中 } while (!q.empty()) { int member = q.front(); q.pop(); // 删除所有入度为0的节点node count++; for (int i = 0; i < graph[member].size(); ++i) { int tmp = graph[member][i]; inDegree[tmp]--; // 删除以node为起点的边 if (inDegree[tmp] == 0) q.push(tmp); } } return count == n; // 如果能全部删除,则序列满足拓扑排序,否则有环。 } int main() { int member, relationship; while (cin >> member >> relationship) { if (member == 0) break; memset(graph, 0, sizeof(graph)); memset(inDegree, 0, sizeof(inDegree)); while (relationship--) { int master, prentice; cin >> master >> prentice; inDegree[prentice]++; graph[master].push_back(prentice); } if (TopologicalSort(member)) { cout << "YES" << endl; } else { cout << "NO" << endl; } } return 0; }