分析题目
求一个图的拓扑序。需要用到拓扑排序。
拓扑排序
将一张图中的顶点以线性方式进行排序，使得对于任何的顶点 \(u\) 到 \(v\) 的有向边 \((u,v)\), 都可以有 \(u\) 在 \(v\) 的前面。
并且拓扑排序只能在有向无环图（DAG）中完成。
做法：每次找到入度为 \(0\) 的顶点，将这个顶点列入拓扑序中，并将这个顶点及其相连的边删去。
删去之后再找到入度为 \(0\) 的顶点，重复以上操作，直到所有点都被删去。至此拓扑排序完成。
代码
BFS
考虑建图时开一个数组 \(ind\)，\(ind_i\) 表示编号为 \(i\) 的顶点的入度数量。
然后进行拓扑排序：
定义一个队列 \(q\) 为上一次操作中被删去的入度为 \(0\) 的点。
首先遍历 \(ind\) 数组，找出入度为 \(0\) 的顶点，存入队列 \(q\)，并纳入拓扑序。
每次取出 \(q\) 的队首，遍历它所有的出边，将与它相连的所有顶点的 \(ind\) 减去 \(1\)（相当于删去与它相连的边的操作）。判断如果 \(ind_i=0\)，那么将这个点也放入队列中等待操作，并也将这个点纳入拓扑序。
重复操作，直到队列为空（整个过程相当于BFS）。
代码实现：
#include <bits/stdc++.h>
#define int long long
const int N = 1005;
using namespace std;
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-'){
w = -1;
}
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
struct edge{
int nxt,to;
}e[N];
int cnt = 0,head[N];
void edge_add(int x,int y){
cnt++;
e[cnt].nxt = head[x];
head[x] = cnt;
e[cnt].to = y;
}
int n,ind[N];
void topo(){
queue<int>q;
for (int i = 1;i <= n;i++){
if (!ind[i]){
q.push(i);
printf("%lld ",i);
}
}
while (!q.empty()){
int tmp = q.front();
q.pop();
for (int i = head[tmp];i;i = e[i].nxt){
int v = e[i].to;
ind[v]--;
if (!ind[v]){
q.push(v);
printf("%lld ",v);
}
}
}
}
signed main(){
n = read();
for (int i = 1;i <= n;i++){
int x = read();
while (x){
edge_add(i,x);
ind[x]++;
x = read();
}
}
topo();
return 0;
}