HRBUST-1631.技能修炼(拓扑排序)

╰半橙微兮° 2022-02-13 08:53 158阅读 0赞

# [HRBUST-1631.技能修炼][HRBUST-1631.] #

### Description ###

寒假第三次周赛强势袭来，首先祝愿大能依靠自己所学的取得一个好成绩。学习之余，我们在这里说一个有关游戏的问题，你来解决一下。一般的游戏中人物技能在修炼时有个特点，就是后面的技能一般都要修炼了前面的某些个才可以修炼。比如10级有一个技能火弹术，20级有一个火焰术，那么此时假如你没修炼10级的火弹，你就不能直接修20级的火焰术，就是这样的道理。现在的问题是，给定一些个技能间的依赖关系，你来写程序来判断该以什么样的顺序来修炼这些技能。为了简化问题，我们用数代表不同的技能，一个数代表一种技能，输入形式N1 N2则代表N1是N2的前置技能。

### Input ###

本题有多组测试数据，每组中第一行为两个数N(1 <= N <= 500)和M(1 <= M <= N\*(N-1)/2)，其中N表示技能总数，接下来有M行。每行是代表两个技能的数字N1和N2，表示N1是N2的前置技能。

### Output ###

对每组测试数据，输出确定下来的技能修炼顺序，要求对于输入的每组数据，输出一行，一行中各技能之间以一个空格间隔（行尾不该有空格而是换行符）。

注意，对于排序的结果可能不是唯一的，这时要求先输出代表技能的数较小的。

### Sample Input ###

4 3
    
    1 2
    
    2 3
    
    4 3

### Sample Output ###

1 2 4 3

### Hint ###

对于上面的样例中2和4都是3的前置技能，但是数字2较小，因此先输出2。

### 拓扑排序 ###

因为题目要求按基数小的优先输出，所以可以用二叉堆来保存入度为0的点。

#include <iostream>
    #include <queue>
    #include <vector>
    #include <algorithm>
    using namespace std;
    int n,m;
    vector<vector<int>> vec;
    vector<int> a;
    vector<int> deg; //记录每个点的入度
    priority_queue<int,vector<int>,greater<int>> q; // 保存入度为0的点
    void toporder(){ 
        for(int i = 1;i <= n;i++){ 
            if(deg[i] == 0) q.push(i);
        }
        while(!q.empty()){ 
            int x = q.top();
            q.pop();
            a.push_back(x);
            for(int i = 0;i < (int)vec[x].size();i++){ 
                int y = vec[x][i];
                deg[y]--;
                if(deg[y] == 0) q.push(y);
            }
        }
    
    }
    int main(){ 
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        std::cout.tie(nullptr);
        cin >> n >> m;
        vec.resize(n+1);
        deg.resize(n+1);
        for(int i = 0;i < m;i++){  // 构建邻接表
            int x,y;
            cin >> x >> y;
            vec[x].push_back(y);
            deg[y]++;
        }
        toporder();
        for(int i = 0;i < (int)a.size();i++){ 
            cout << a[i] <<" ";
        }
        cout << endl;
        return 0;
    
    }

[HRBUST-1631.]: http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1631