6.4.3 拓扑排序

好吧,笔者开单章开上瘾了,话不多说,先来一个拓扑排序,笔者最初自己写的时候并没有使用拓扑排序吧

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

上一篇:POJ2689 ZOJ1842 UVA10140 Prime Distance【筛选法】


下一篇:Prime Distance