好吧,笔者开单章开上瘾了,话不多说,先来一个拓扑排序,笔者最初自己写的时候并没有使用拓扑排序吧
Ordering_Tasks题解
点击查看笔者代码
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int maxl = 100+5;
int cntr[maxl], cntc[maxl], mat[maxl][maxl];
bool isOut[maxl];
bool check(int (&a)[maxl], int& n){
for(int i = 1; i <= n; i++)
if(a[i]) return true;
return false;
}
void del(int& val, int& n) {
cntr[val] = cntc[val] = 0;
for(int i = 1; i <= n; i++) {
if(mat[val][i]) {
mat[val][i] = 0;
cntc[i]--;
}
if(mat[i][val]) {
mat[i][val] = 0;
cntr[i]--;
}
}
}
int main() {
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
int n, m;
while(scanf("%d%d", &n, &m) == 2 && (n||m)) {
memset(mat, 0, sizeof(mat));
memset(isOut, 0, sizeof(isOut));
memset(cntr, 0, sizeof(cntr));
memset(cntr, 0, sizeof(cntc));
int x, y, flag = 0;
for(int i = 0; i < m; i++) {
cin >> x >> y;
if(!mat[x][y]) {
mat[x][y] = 1;
cntr[x]++;
cntc[y]++;
}
}
vector<int> output;
while(check(cntr, n)) {
output.clear();
for(int i = 1; i <= n; i++)
if(cntr[i] && !cntc[i]) output.push_back(i);
for(int i = 0; i < output.size(); i++) {
isOut[output[i]] = 1;
if(flag) cout << " ";
if(!flag) flag = 1;
cout << output[i];
del(output[i], n);
}
}
for(int i = 1; i <= n; i++)
if(!isOut[i]) {
if(flag) cout << " ";
if(!flag) flag = 1;
cout << i;
}
cout << endl;
}
return 0;
}
很暴力的一种simulate思想,这题的难点不是很多,笔者的思想类似一个大擂台,没有出现的数字就是最大的,后面随便排就好了,而出现的数字,不断地找到最小的数字,淘汰掉就可以了,是的,优胜劣汰,又是一种新的递归思想,不过,需要注意的是本题的一大坑点,m可以为0,这题不能以n && m作为终止条件,而是需要考虑到m==0的特殊情况,呜呜,我的first blood