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

相关推荐

门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
代码飞升:别用口语,后端就写后端,前端就写前端,最后别光后悔
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务