颓了好久终于写了个题了
题目链接
思路
给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。
设从(x)点出发能到达的点构成的集合(f(x))
[f(x)={x} cupBigg(igcup f(y)Bigg)(x,y联通)
]
发现从(x)出发能到的点，是从(x)的各个后继节点(y)出发能到的点的并集(用状态压缩来表示状态)，所以我们可以拓扑排序求出拓扑序，然后倒序计算
代码
#include<bits/stdc++.h>
#include<bitset>
using namespace std;
const int N=30011;
queue<int>q;
bitset<N>f[N];
int du[N],n,m,cnt,head[N],tp[N],len;
struct node {
int u,v,Next;
} e[N];
void add(int u,int v) {
e[++cnt].u=u;
e[cnt].v=v;
e[cnt].Next=head[u];
head[u]=cnt;
}
void topsort() {
for(int i=1; i<=n; ++i) if(du[i]==0) q.push(i);
while(!q.empty()) {
int to=q.front();
q.pop();
tp[++len]=to;
for(int i=head[to]; i; i=e[i].Next) {
int To=e[i].v;
if((--du[To])==0) q.push(To);
}
}
}
int main() {
cin>>n>>m;
for(int i=1; i<=m; ++i) {
int x,y;
cin>>x>>y;
add(x,y);
du[y]++;
}
topsort();
for(int i=len; i>=1 ; --i) {
int u=tp[i];
f[u][u]=1;
for(int j=head[u]; j; j=e[j].Next) {
int v=e[j].v;
f[u] |= f[v];
}
}
for(int i=1; i<=n; ++i) {
cout<<f[i].count()<<'
';
}
return 0;
}
错误原因
1.bitset开小了
2.f[u] |= f[v];写成了f[i]|=f[v];我真是太二了