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;
}