题目链接
题意分析
实现拓扑排序
解题思路
用邻接表存储有向图,按拓扑排序算法解决即可!
AC程序(C++)
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn =
110;
int N, M;
struct Node{
int id, count;
Node() {
count =
0;
}
}node[maxn];
vector<int> Adj[maxn];
void topsort() {
queue<int> Q;
for(
int i =
1; i <= N; i++) {
if(node[i].count ==
0)
Q.push(i);
}
int num =
0;
while(!Q.empty()) {
num++;
int v = Q.front();
Q.pop();
printf(
"%d", v);
if(num == N)
printf(
"\n");
else printf(
" ");
for(
int i =
0; i < Adj[v].size(); i++){
if(--node[Adj[v][i]].count ==
0)
Q.push(Adj[v][i]);
}
}
}
int main() {
int a, b;
while(
true) {
scanf(
"%d %d", &N, &M);
if(N ==
0 && M ==
0)
break;
for(
int i =
1; i < maxn; i++) Adj[i].clear();
for(
int i =
1; i <= M; i++) {
scanf(
"%d %d", &a, &b);
Adj[a].push_back(b);
node[b].count++;
}
topsort();
}
return 0;
}