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;
}
全部评论

相关推荐

10-09 09:39
门头沟学院 C++
HHHHaos:这也太虚了,工资就一半是真的
点赞 评论 收藏
分享
AaronRuan:看到了好多开奖了,不知道为啥自己也有点激动,真的替你们感到高兴啊
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务