首页 > 编程语言 > 详细

HDU-1285-确定比赛名次(拓扑排序)

时间:2019-01-12 17:27:44      阅读:58      评论:0      收藏:0      [点我收藏+]

标签:bits   取出   its   queue   greate   fir   比赛   c++   out   

  • 拓扑排序
    #include "bits/stdc++.h"
    using namespace std;
    // 用来存某个点的入度数量
    int num[505];
    // 用来存某个节点的出度
    set<int> outde[505];
    int ans[505];
    priority_queue<int, vector<int>, greater<int> > qu;
    int main() {
        int n, m, id, victory, defeat;
        while (~scanf("%d%d", &n, &m)) {
            id = 0;
            while (m--) {
                scanf("%d%d", &victory, &defeat);
                // 去重,这题的坑点,输入数据可能会重复defeat被victory多次打败
                if (outde[victory].count(defeat) == 0) {
                    num[defeat]++;
                    outde[victory].insert(defeat);
                }
            }
            // 把入度为0的点加入优先队列
            for (int i = 1; i <= n; i++) {
                if (num[i] == 0) {
                    qu.push(i);
                }
            }
            while (!qu.empty()) {
                // 取出优先队列中编号最小的点并存到ans数组中去;
                int first = qu.top();
                qu.pop();
                ans[++id] = first;
                // 将first的所以出度的入度数量减1;
                for (int i : outde[first]) {
                    num[i]--;
                    // 如果入度变成了0,就加入优先队列
                    if (num[i] == 0) {
                        qu.push(i);
                    }
                }
                outde[first].clear();
            }
            for (int i = 1; i < n; i++) {
                printf("%d ", ans[i]);
            }
            printf("%d\n", ans[n]);
        }
        return 0;
    }

     NOTE : 每次将入度为0的点添加到ans末尾的做法是错误的;

HDU-1285-确定比赛名次(拓扑排序)

标签:bits   取出   its   queue   greate   fir   比赛   c++   out   

原文:https://www.cnblogs.com/Angel-Demon/p/10260117.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号