蓝书（算法竞赛进阶指南）刷题记录——CH2101可达性统计（拓扑排序+bitset）

题目&＃xff1a;CH2101.
题目大意&＃xff1a;给定一张$n$个点$m$条边的有向无环图&＃xff0c;求每个点可以达到多少个点.
1≤n,m≤3∗1041\leq n,m\leq 3*10^41≤n,m≤3∗104.

很容易想到先跑一个拓扑排序&＃xff0c;从出度为$0$的点开始逆推回来.

但是直接求和很明显会有重复&＃xff0c;所以考虑每个点$i$记录一个集合$b[i]$表示$i$可以到达这个集合里的数.

那么显然&＃xff1a;
b[x]&＃61;⋃(x,y)∈Eb[y]b[x]&＃61;\bigcup_{(x,y)\in E}b[y] b[x]&＃61;(x,y)∈E⋃​b[y]

然后用bitset实现这个集合即可&＃xff0c;时间复杂度O(n(n&＃43;m)32)O(\frac{n(n&＃43;m)}{32})O(32n(n&＃43;m)​)&＃xff0c;空间复杂度O(n28)O(\frac{n^2}{8})O(8n2​).

代码如下&＃xff1a;

#include using namespace std;#define Abigail inline void
typedef long long LL;const int N&＃61;30000;struct side{int y,next;
}e[N&＃43;9];
int lin[N&＃43;9],top,n,m;void ins(int x,int y){e[&＃43;&＃43;top].y&＃61;y;e[top].next&＃61;lin[x];lin[x]&＃61;top;
}int deg[N&＃43;9],ord[N&＃43;9],co,ans[N&＃43;9];
bitset<N&＃43;9>b[N&＃43;9];
queue<int>q;void topsort(){for (int i&＃61;1;i<&＃61;n;&＃43;&＃43;i)if (!deg[i]) q.push(i);while (!q.empty()){int t&＃61;q.front();q.pop();ord[&＃43;&＃43;co]&＃61;t;for (int i&＃61;lin[t];i;i&＃61;e[i].next){--deg[e[i].y];if (!deg[e[i].y]) q.push(e[i].y); }}for (int i&＃61;co;i>&＃61;1;--i){int t&＃61;ord[i];b[t][t]&＃61;1;for (int j&＃61;lin[t];j;j&＃61;e[j].next)b[t]|&＃61;b[e[j].y];ans[t]&＃61;b[t].count();}
}Abigail into(){scanf("%d%d",&n,&m);int x,y;for (int i&＃61;1;i<&＃61;m;&＃43;&＃43;i){scanf("%d%d",&x,&y);ins(x,y);&＃43;&＃43;deg[y];}
}Abigail work(){topsort();
}Abigail getans(){for (int i&＃61;1;i<&＃61;n;&＃43;&＃43;i)printf("%d\n",ans[i]);
}int main(){into();work();getans();return 0;
}