代码
/*
* Project: 0x21_树与图的遍历
* File Created:Tuesday, January 26th 2021, 7:31:09 pm
* Author: Bug-Free
* Problem:Acwing 164. 可达性统计
*/
#include <algorithm>
#include <bitset>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 3e4 + 10;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N], seq[N]; //入度， 拓扑序列
bitset<N> f[N];
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
// 只有有向无环图， 才能做拓扑排序
// 拓扑排序
void topsort() {
queue<int> q;
// 先把所有入度为 0 的点加入队列（有向图）
for (int i = 1; i <= n; i++) {
if (!d[i]) {
q.push(i);
}
}
// k表示当前拓扑排序中元素的个数
int k = 0;
while (q.size()) {
int t = q.front();
q.pop();
seq[k++] = t; //将队头元素加入拓扑序中
//将当前点可以到的点的入度--（删去x连向其他点的边）
for (int i = h[t]; ~i; i = ne[i]) { // 遍历这个点所有的邻边
int j = e[i]; // e[i] 表示 邻边所对应的终点
if (--d[j] ==
0) { //如果j这个点的入度为0了，那我们就可以加到队列中去
q.push(j);
}
}
}
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
add(a, b);
d[b]++; //有一条 a 指向 b的边， 因此b的入度+1
}
topsort();
// 从后往前递推
// bitset<N> s;
// s[k] 表示 第k位， 既可以取值， 也可以赋值
for (int i = n - 1; i >= 0; i--) {
int j = seq[i];
f[j][j] = 1; // j这个点可以到达自己 f[j][j] =表示从 j出发的点，
// 能够到的点（1表示可以到， 0表示不能到），j可以到自己，
// 因此f[j][j]=1
for (int k = h[j]; ~k; k = ne[k]) { //所有能到到达的点
f[j] |= f[e[k]]; // j这个点可以到达的点的数量= {j} U {y1} U {y2}
// ... {yn}
}
}
for (int i = 1; i <= n; i++) {
// f[i].count() 返回f[i] 中 1的个数
cout << f[i].count() << endl;
}
return 0;
}
//可以直接倒序遍历 #include<cstdio> #include<cstring> #include<bitset> using namespace std; const int N = 30010,M = 30010; int n,m,idx,h[N],e[M],ne[M],q[N],din[N]; bitset<N> w[N]; void add(int a,int b){ e[idx] = b,ne[idx] = h[a],h[a] = idx++; } void topsort(){ int hh = 0,tt = -1; for(int i = 1;i <= n;++i) if(!din[i]) q[++tt] = i; for(int i = 1;i <= n;++i) w[i][i] = 1;//本身可达 while(hh <= tt){ int t = q[hh++]; //w[t][t] = 1;//err:丢出来就已经确定了，不能重置 for(int i = h[t];~i;i = ne[i]){ int j = e[i]; w[j] |= w[t]; if(--din[j] == 0) q[++tt] = j; } } } int main(){ scanf("%d%d",&n,&m); memset(h,-1,sizeof h); while(m--){ int a,b; scanf("%d%d",&a,&b); add(b,a); ++din[a]; } topsort(); for(int i = 1;i <= n;++i) printf("%d\n",w[i].count()); return 0; }你跟我想的一模一样，我前面奖金那题也用了倒序，一下子就做出来了，但是这题我想到了倒序，唯一一点就是不知道这个bitset，然后没做出来
你可以在找入度为0的点的时候，顺便将所有点都本身可达初始化w为1，那样可以节省一个循环
f[N]不是一维的吗， 为什么可以用f[j][j]
bitset 支持询问某一个数的第几位二进制，所以可以用 f[j][j]，意思就是第 j 个数的第 j 二进制数是多少（也可以支持修改）
感谢大佬~
不用蟹~
还不会拓扑排序的伙伴们看下这篇博客，感觉讲得很好！
请问为啥重边不影响答案啊
bitnet用的很妙
我竟然看懂了，果断收藏
%%%%%%%%%%%%%%%%%
Orz
Segmentation Fault
求助
#include<iostream> #include<queue> #include<algorithm> #include<cstring> #include<bitset> using namespace std; const int N=30010; int a,b,n,m,cnt=0,cn=0,head[N],mon[N],so[N]; bitset<N> f[N]; struct node{ int next,to; }sb[20005]; void add(int a,int b){ sb[++cnt].next=head[a],head[a]=cnt,sb[cnt].to=b; so[b]++; } void topu(){ queue<int> s; for(int i=1;i<=n;i++) if(!so[i]) s.push(i); while(s.size()){ int t=s.front(); s.pop(); mon[++cn]=t; for(int i=head[t];i;i=sb[i].next){ int tt=sb[i].to; if(--so[tt]==0){ s.push(tt); } } } } int main(){ cin>>n>>m; memset(head,0,sizeof head); for(int i=1;i<=m;i++){ cin>>a>>b; add(a,b); } topu(); for(int i=1;i<=n;i++){ int t=mon[n-i+1]; f[t][t]=1; for(int j=head[t];j;j=sb[j].next){ f[t]|=f[sb[j].to]; } } for(int i=1;i<=n;i++) cout<<f[i].count()<<endl; return 0; }写的太细了，对萌新太友好了，棒！
写的太好了！兹磁作者qwq