2101 可达性统计

末蓝、 2022-01-07 16:27 202阅读 0赞

## [**2101 可达性统计**][2101] ##

> #### 描述 ####
> 
> 给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。N,M≤30000。
> 
> #### 输入格式 ####
> 
> 第一行两个整数N,M，接下来M行每行两个整数x,y，表示从x到y的一条有向边。
> 
> #### 输出格式 ####
> 
> 共N行，表示每个点能够到达的点的数量。

*  用f(x)表示从x出发能到达的点的集合，则它相当于从x的各个后继出发能到的点得并集再加上x本身，所以说在计算出x的所有后继节点的f值后就能得到x的f值。所以用到拓扑排序
 *  我们先求出一个拓扑序，然后按拓扑序倒着计算——因为拓扑序中保证了对于任意的(x,y)，x都排在y之前。
 *  利用bitset表示每个点能到达的点

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <cstdio>
     2 #include <iostream>
     3 #include <algorithm>
     4 #include <cstring>
     5 #include <queue>
     6 #include <bitset>
     7 using namespace std;
     8 
     9 #define res register int
    10 const int N=30000+10;
    11 int head[N],ver[N<<1],nxt[N<<1],deg[N],n,m,tot(0);
    12 int a[N],cnt(0);
    13 bitset<N> f[N];
    14 
    15 inline void add(int x,int y) {
    16     ver[++tot]=y; nxt[tot]=head[x]; head[x]=tot;
    17 }
    18 
    19 queue<int> q;
    20 inline void toposort()
    21 {
    22     for(res i=1 ; i<=n ; i++) if(!deg[i]) q.push(i);
    23     while(q.size())
    24     {
    25         int x=q.front(); q.pop(); a[++cnt]=x;
    26         for(res i=head[x] ; i ; i=nxt[i])
    27         {
    28             int y=ver[i];
    29             if((--deg[y])==0) q.push(y);
    30         }
    31         
    32     }
    33 }
    34 
    35 int main()
    36 {
    37     scanf("%d %d",&n,&m);
    38     for(res i=1 ; i<=m ; i++)
    39     {
    40         int x,y; scanf("%d %d",&x,&y);
    41         add(x,y); deg[y]++;
    42     }
    43     toposort();
    44     for(res i=cnt ; i>=1 ; i--)
    45     {
    46         int x=a[i];
    47         f[x][x]=1;
    48         for(res j=head[x] ; j ; j=nxt[j])
    49         {
    50             int y=ver[j];
    51             f[x]|=f[y];
    52         }
    53     }
    54     for(res i=1 ; i<=n ; i++) printf("%d\n",f[i].count());
    55     return 0;
    56 }

转载于:https://www.cnblogs.com/wmq12138/p/10367962.html

[2101]: http://contest-hunter.org:83/contest/0x20%E3%80%8C%E6%90%9C%E7%B4%A2%E3%80%8D%E4%BE%8B%E9%A2%98/2101%20%E5%8F%AF%E8%BE%BE%E6%80%A7%E7%BB%9F%E8%AE%A1
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/f9c32638b6d944eba908db9e1487bf18.png