给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。

输入格式

第一行两个整数N,M，接下来M行每行两个整数x,y，表示从x到y的一条有向边。

输出格式

输出共N行，表示每个点能够到达的点的数量。

数据范围

1≤N,M≤300001≤N,M≤30000

输入样例：

10 103 82 32 55 95 92 33 94 82 104 9

输出样例：

1633211111

 

算法：拓扑排序 + 状态压缩算法

题解：首先求出该有向无环图的拓扑序列，根据拓扑序列的性质：在拓扑序种，对于任意一条边(x, y)来说，x都会排在y之前（读者可以自行画图证明）。然后倒叙遍历拓扑序来结果状态压缩来求的结果。

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int maxn = 3e4+7;vector
          
            g[maxn];vector
           
             a;bitset
            
              f[maxn];int in[maxn];int n, m;void topsort() { queue
             
               q; for(int i = 1; i <= n; i++) { if(in[i] == 0) { q.push(i); } } while(!q.empty()) { int u = q.front(); q.pop(); a.push_back(u); //记录拓扑序列 int len = g[u].size(); for(int i = 0; i < len; i++) { int v = g[u][i]; if(--in[v] == 0) { q.push(v); } } }}void sovle() { for(int i = a.size() - 1; i >= 0; i--) { int u = a[i]; f[u].reset(); //清空数组 f[u][u] = 1; //将当前位置赋1 int len = g[u].size(); for(int j = 0; j < len; j++) { int v = g[u][j]; f[u] = f[u] | f[v]; //将经过的点的状态压缩到当前数组中 } }}int main() { scanf("%d %d", &n, &m); for(int i = 1; i <= m; i++) { int u, v; scanf("%d %d", &u, &v); g[u].push_back(v); in[v]++; } topsort(); sovle(); for(int i = 1; i <= n; i++) { printf("%d\n", f[i].count()); } return 0;}