2016年3月22日 星期二

(uva 10305) topological sort

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

const int MAX_N = 103;
vector<int> edg[MAX_N];
bool visit[MAX_N];
int who_get_stamp[MAX_N];

void dfs_for_stamp(int now,int &cur_stamp) {
visit[now]=true;
int len=edg[now].size();
for (int x=0;len>x;x++) {
int j=edg[now][x];
if (visit[j]==false) dfs_for_stamp(j,cur_stamp);
}
who_get_stamp[cur_stamp++]=now;
}

int main () {
int n,m;
while (scanf("%d %d",&n,&m) != EOF) {
if (!n&&!m) return 0;
for (int x=0;n>=x;x++) edg[x].clear();
while (m--) {
int i,j;
scanf("%d %d",&i,&j);
edg[i].push_back(j);
}
for (int x=0;n>=x;x++) visit[x]=false;
int stamp=0;
for (int x=1;n>=x;x++) {
if (visit[x]==false) {
dfs_for_stamp(x,stamp);
}
}
for (int x=n-1;x>=0;x--) {
if (x!=n-1) printf(" ");
printf("%d",who_get_stamp[x]);
}
puts("");
}
}

沒有留言:

張貼留言