拓扑排序算法——基于可达性分析

可达性统计分析

对于一个包含N个顶点和M条边的有向无环图，需要分别计算从每个顶点出发可以抵达的顶点总数。

输入形式
首行给出两个整数N和M，随后M行中每行包含两个整数x和y，表示存在一条从x指向y的有向边。

输出形式
共输出N行，每行对应一个顶点能够到达的顶点数目。

数据规模
1≤N,M≤30000
输入示例：
10 10
3 8
2 3
2 5
5 9
5 9
2 3
3 9
4 8
2 10
4 9
输出示例：
1
6
3
3
2
1
1
1
1
1

题解：

通过绘制关系图可知，我们能够依据出发点对指向其的节点信息进行更新。因此，我们采用逆向拓扑排序的方式，并结合动态规划方法进行处理。在此过程中，运用了状态压缩的思路以有效降低算法的时间复杂度。

    #include <bits/stdc++.h>
    using namespace std;
    const int N=3e4+7;
    int w[N],cnt,t,ne[N],head[N],e[N],d[N],n,m;
    void add(int a,int b)
    {
    e[cnt]=b,ne[cnt]=head[a],head[a]=cn