题目大意:给定一张N个点M条边的有向无环图,分别统计从每个点出发能够到达的点的数量。
思路:
从x出发能够到达的点构成的集合f(x)
有 f(x)= {x} ∪f(y) (其中y为存在的有向边(x,y))
这启发我们用拓扑排序算法求出一个拓扑序列,然后按照拓扑序列的倒序进行计算。因为对于任意一条有向边(x,y)x都排在y之前。
用状态压缩对于每个f(x),其中di I位表示的是x能到i,0则表示不能。
我们可以用bitset来做、
code:
#include<bits/stdc++.h>
using namespace std;
const int N=30010;
int tot,n,m,cnt;
int deg[N];
int ne[N],ver[N],head[N];
int a[N];
void add(int x,int y){
ver[++tot]=y,ne[tot]=head[x],head[x]=tot;
deg[y]++;
}
void topsort(){
queue<int> q;
for(int i=1;i<=n;i++)
if(deg[i]==0) q.push(i);
while(!q.empty()){
int x=q.front();q.pop();
a[++cnt]=x;
for(int i=head[x];i;i=ne[i]){
int y=ver[i];
if(--deg[y]==0) q.push(y);
}
}
}
bitset<N> tp[N];
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;cin>>x>>y;
add(x,y);
}
cnt=0;
topsort();
for(int i=1;i<=n;i++){
tp[i][i]=1;
}
for(int k=cnt;k>=1;k--){
for (int i=head[a[k]];i;i=ne[i]){
int y=ver[i];
tp[a[k]]|=tp[y];
}
}
for(int i=1;i<=n;i++) printf("%d\n",tp[i].count());//统计1的个数
}