ReZero's Utopia.

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

Word count: 722Reading time: 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();
}
}
}``````

#### 原题如上，旭哥思路的代码

``````#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排序保证字典序

Author：ReZero