拓朴排序与动态规划

一、知识部分

1 概念

如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。
拓扑排序指是将一个DAG图中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边$<u,v>\in E(g)$，则u在线性序列中出现在v之前。

2 实现

Step 1:选择一个入度为0的点输出；
Step2:删除此节点及其所有出边；
Step3:重复执行1,2，直至图空。
例：
原图：

输出0。
。
输出1。

输出3

输出2。

输出4。
此时图空了，拓扑序列为0,1,3,2,4

2.1 使用BFS

首先将入度为0的顶点入队；
while(队列不空){队头的所有邻接点入度-1；如果存在邻接点入度变为0时则入队；出队；
}
出队序列就是拓扑序列；

这样得到的拓扑序列不唯一。那如何使拓扑序列的字典序最小呢？
将队列替换为优先队列。

2.2 使用DFS

每次都沿着一条路径一直向下搜索，直到某个顶点出度为0被标记已经访问，就停止递归，往回走，在回来的路上记录拓扑排序，即后序遍历。（所以我们得到的序列的反着的，反转一下就好了）

二、实践

1 家谱树

1.1 题目描述

请你整理一下一个家谱。 给出每个人的孩子的信息。 输出一个序列，使得每个人的后辈都比那个人后列出。
第1行一个整数 $N(1\le N\le 100)$ ，表示家族的人数； 接下来 $N$ 行，第 $I$ 行描述第$I$ 个人的儿子； 每行最后是0表示描述完毕。
如果有多解输出字典序最小的解。

1.2 思路

字典序最小，使用优先队列。
用vector更简洁。

1.3 AC代码

#include<bits/stdc++.h>
#define ll long long
#define bug printf("___OK___")
#define pr printf("\n")
#define pa printf("A: ")
#define pi acos(-1.0)
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;
int n;
vector<vector<int> >e(1000);
int d[1002];
void bfs(){//入队for(int i=1;i<=n;i++){if(d[i]==0){q.push(i);}}while(!q.empty()){ll k=q.top();q.pop();printf("%d ",k);for(int i=0;i<e[k].size();i++){d[e[k][i]]--;//队头的所有邻接点入度--if(!d[e[k][i]]){q.push(e[k][i]);}}}
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){int x;while(scanf("%d",&x)&&x!=0){//i到x有一条边e[i].push_back(x);d[x]++;//记录每个点的入度}}bfs();return 0;
}

2 食物链2

2.1 题目描述

现在给你 $n$ 个物种和 $m$ 条能量流动关系，求其中的食物链条数。物种的名称为从 $1$ 到 $n$ 编号 $M$ 条能量流动关系形如 $a_1,b_1,a_2,b_2,a_3,b_3,\dots ,a_{m-1},b_{m-1},a_m,b_m$。其中 $a_i$ 和 $b_i$ 表示能量从物种 $a_i$ 流向物种 $b_i$，注意单独的一种孤立生物不算一条食物链。

2.2 思路

入度为零的点的方案数为1，其余的点的方案数等于指向它的点的方案数之和，最后统计出度为0的点的方案数，累加即可。
此时用了一点点DP。
注意到单独的一种孤立生物不算一条食物链，那么在一开始入度为零的点进入队列时要判断一下，不让那些没有出度的点进入队列。

2.3 AC代码

#include<bits/stdc++.h>
#define ll long long
#define bug printf("___OK___")
#define pr printf("\n")
#define pa printf("A: ")
#define pi acos(-1.0)
using namespace std;
const int N=1000010;
ll n,m,f[N],d[N];
vector<ll> e[N];
ll ans;
ll bfs(){queue<ll> q;for(int i=1;i<=n;i++){if(!d[i]&&e[i].size()){q.push(i);f[i]=1; }}	while(!q.empty()){ll x=q.front();q.pop();if(!e[x].size()){ans+=f[x];}for(int i=0;i<e[x].size();i++){ll t=e[x][i];f[t]+=f[x];d[t]--;if(!d[t]){q.push(t);}}}return ans;
}
int main(){cin>>n>>m;for(int i=1;i<=m;i++){ll x,y;cin>>x>>y;d[y]++;e[x].push_back(y);}cout<<bfs();return 0;
}