ReZero's Utopia.

拓扑排序问题(队列实现)

字数统计: 678阅读时长: 3 min
2016/10/23 Share

拓扑排序

方法:

  1. 找到所有入度为0的点插进队列
  2. 选择一个并输出它
    • 然后删掉与之关联的所有边(即任何与之相连的入度-1)
    • 删除过程遇到入度为0点插入队列
  3. 重复第二步,直到队列中无0点

优化:如果要求最小字典序

用反向拓扑加优先队列

#include <bits/stdc++.h>

using namespace std;

vector<int> G[5020];
map<string, int> maps;
map<int, string> mapr;

struct less_cmp{
    bool operator()(const int &a, const int &b){
        return mapr[a] > mapr[b];
    }
};

int main(){
    int T;
    cin >> T;
    for(int kase = 1; kase <= T; ++kase){
        int n, m, in[5020], cnt = 0, ans[5020];
        cin >> n;
        for(int i = 0; i < n; ++i){
            string cla;
            cin >> cla;
            maps.insert(pair<string, int>(cla, i));
            mapr.insert(pair<int, string>(i, cla));
        }
        cin >> m;
        for(int i = 0; i < m; ++i){
            string as, bs;
            cin >> as >> bs;
            int u = maps[as], v = maps[bs];
            G[u].push_back(v);
            in[v]++;
        }
        priority_queue<int, vector<int>, less_cmp > que;
        for(int i = 0; i < n; ++i){
            if(in[i] == 0)
                que.push(i);
        }
        vector<int>::iterator iter;
        while(!que.empty()){
            int temp = que.top();
            que.pop();
            ans[cnt++] = temp;
            for(iter = G[temp].begin(); iter != G[temp].end(); ++iter){
                    if(--in[*iter] == 0){
                        que.push(*iter);
                    }
                }
        }
        cout << "Case " << kase << ":" << endl;
        for(int i = 0; i < cnt; ++i){
            cout << mapr[ans[i]] << endl;
        }
        maps.clear();
        mapr.clear();
        for(int i = 0; i < 5020; ++i){
            G[i].clear();
        }
    }
}

开心的wrong answer-_-

第一行为样例组数T。每组样例第一行为课程数量n(1 <= n <= 5000),以下n行每行表示一门课程名称。接下来为关系数量m(1 <= m <= 10000),每一行有两个课程名称a、b,表示a课程要开设在b课程前面。(输入保证无环)

原题如上,旭哥思路的代码

#include <bits/stdc++.h>

using namespace std;
vector<int> G[5020];
string mapr[5020];
map<string, int> maps;

int main(){
    int T;  scanf("%d", &T);
    for(int kase = 1; kase <= T; ++kase){
        int n, m, in[5020] = {0}, cnt = 0, ans[5020];

        scanf("%d", &n);
        for (int i = 0; i < n; ++i) G[i].clear();
        maps.clear();
        for(int i = 0; i < n; ++i){
            char as[44];
            scanf("%s", as);
            mapr[i] = as;
        }
        sort(mapr, mapr + n);
        for(int i = 0; i < n; ++i){
            maps[mapr[i]] = i;
        }

        scanf("%d", &m);
        for(int i = 0; i < m; ++i){
            char as[44], bs[44];
            scanf("%s %s", as, bs);
            int u = maps[as], v = maps[bs];
            G[u].push_back(v);
            ++in[v];
        }

        printf("Case %d:\n", kase);
        for(int i = 0; i < n; ++i){
            int temp = 0;
            for(int j = 0; j < n; ++j){
                if(!in[j]){
                    printf("%s\n", mapr[j].c_str());
                    temp = j; --in[j];
                    break;
                }
            }
            for(int k = 0; k < G[temp].size(); ++k){
                --in[G[temp][k]];
            }
        }
    }
}
  • 权值置-1,排除节点
  • G(vector)来控制制约关系
  • sort排序保证字典序
CATALOG
  1. 1. 拓扑排序
    1. 1.0.1. 方法:
    2. 1.0.2. 优化:如果要求最小字典序
    3. 1.0.3. 原题如上,旭哥思路的代码