拓扑排序
方法：
- 找到所有入度为0的点插进队列
- 选择一个并输出它
- 然后删掉与之关联的所有边（即任何与之相连的入度-1）
- 删除过程遇到入度为0点插入队列
- 重复第二步，直到队列中无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排序保证字典序