基于邻接矩阵实现的拓扑排序:
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
const int N = 110;
int mp[N][N];
int vis[N];
int n, m;
void topo_sort()
{
for(int i=1; i <= n; i++)
{
for(int j=1; j <= n; j++)
{
if(vis[j] == 0)
{
vis[j]--;
printf("%d", j);
if(i != n) printf(" ");
else printf("\n");
for(int k=1; k <= n; k++)
{
if(mp[j][k] == 1)
vis[k]--;
}
break;
}
}
}
}
int main()
{
while(scanf("%d", &n) != EOF)
{
for(int i=0; i<N; i++) vis[i] = 0;
int child;
for(int i=1; i <= n; i++)
{
while(scanf("%d", &child), child)
{
mp[i][child] = 1;
vis[child] ++;
}
}
topo_sort();
}
return 0;
}
基于邻接表 + 优先队列实现的拓扑排序:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 510;
vector<int> mp[N];
int vis[N];
int n, m;
vector<int> ve;
void topo_sort()
{
priority_queue<int, vector<int>, greater<int> > que; // 值越小优先级越高
ve.clear();
for(int i=1; i <= n; i++)
{
if(vis[i] == 0)
{
que.push(i);
vis[i] --;
}
}
while(!que.empty())
{
int v = que.top(); que.pop();
ve.push_back(v);
for(int i=0; i<mp[v].size(); i++)
{
vis[mp[v][i]] --;
if(vis[mp[v][i]] == 0)
que.push(mp[v][i]);
}
}
}
int main()
{
while(scanf("%d %d", &n, &m) != EOF)
{
for(int i=0; i < N; i++)
{
vis[i] = 0;
mp[i].clear();
}
int a, b;
for(int i=0; i<m; i++)
{
scanf("%d %d", &a, &b);
mp[a].push_back(b);
vis[b]++;
}
topo_sort();
for(int i=0; i<n; i++)
printf("%d%c", ve[i], i == n-1 ? '\n' : ' ');
}
return 0;
}