#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int indegree[9];
vector<vector<int> > vv(9);
typedef vector<int>::iterator it;
queue<int> q;
bool flag[9];
void init() {
memset(flag, false, sizeof(bool)*9);
memset(indegree, 0, 9*sizeof(int));
vv[0].push_back(2);++indegree[2];
vv[1].push_back(7);++indegree[7];
vv[2].push_back(6);++indegree[6];
vv[3].push_back(5);++indegree[5];
vv[4].push_back(7);++indegree[7];
vv[6].push_back(3);++indegree[3];
vv[6].push_back(4);++indegree[4];
vv[7].push_back(5);++indegree[5];
vv[8].push_back(1);++indegree[1];
vv[8].push_back(4);++indegree[4];
}
void tsort() {
for (int i = 0; i<=8; i++)
if (indegree[i] == 0 && !flag[i]) {
q.push(i);
while(!q.empty()) {
int number = q.front();
cout << number << ' ';
flag[number]= true;
q.pop();
for ( it ii = vv[number].begin(); ii != vv[number].end(); ++ii) {
--indegree[*ii];
if ( indegree[*ii] == 0)
q.push(*ii);
}
}
}
}
int main(){
init();
tsort();
return 0;
}
topological sort taocp 2.2.3,vol 1
Nov252008
Subscribe to:
Post Comments (Atom)
0 评论: (+add yours?)
Post a Comment