地址:https://www.acwing.com/problem/content/166/
题意:
求每个点所能到达的点数目,包含自身。
解析:
一:已知为有向无环图,那么可以考虑用拓扑排序。
假设有图:
1->2->3->4
5->3
拓扑排序结果:
1->2-5->3->4
那么求每个点所能到达的点,是需要从右往左看的。对于5,它能到达5,3,4。对于2,它能到达2,5,3,4。那么求1所能到达的点,直接累加f[2]和f[5]是不行的,有重复点。所以我们需要求两者并集:f[2]Uf[5]=={2,5,3,4}
如果我们把n个点,看为一个长度为n+1(0不算点)的二进制,f[i][1]==1表示,i点能到1号点,==0则表示不能到。
那么对于一个点,先把它本身f[i][i]标为1,然后遍历它的出边,与它们两两进行 | 运算即可。
二:关于bitset
#include<bitset>
bitset<maxn>f[maxn]
f[].set()表示全变为1,括号内填入 i 表明将第i+1位变1
f[].reset()表示全变为0,括号内填入 i 表明将第i+1位变0
f[].flip()全取反
f[].count()求二进制所含1的数目
为了更直观地说明其在本题的作用,给出测试代码和运行截图:
bitset<5>f[maxn]; int main() { f[1][2]=1;//1->2 f[1][3]=1;//1->3 f[3][2]=1;//3->2 cout<<f[1]<<endl; cout<<f[3]<<endl; f[3]|=f[1];//取并集 cout<<f[3]<<endl; cout<<f[3].count();//求所含1的数目 }
三:AC代码:
#include<iostream> #include<cstring> #include<cstdio> #include<bitset> #include<queue> using namespace std; const int maxn=3e4+10; int ans[maxn],tot=0; int e[maxn],ne[maxn],idx,h[maxn],d[maxn]; int n,m; bitset<maxn>f[maxn]; void init() { memset(h,-1,sizeof(h)); idx=0; } void add(int a,int b) { e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } void bfs() { queue<int>q; for(int i=1;i<=n;i++) if(d[i]==0) q.push(i); while(!q.empty()) { int t=q.front(); q.pop(); ans[tot++]=t; for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; d[j]--; if(d[j]==0) { q.push(j); } } } } int main() { cin>>n>>m; init(); for(int i=1;i<=m;i++) { int a,b; cin>>a>>b; add(a,b); d[b]++; } bfs(); for(int i=tot-1;i>=0;i--) { int now=ans[i]; f[now][now]=1; for(int j=h[now];j!=-1;j=ne[j]) { f[now]|=f[e[j]]; } } for(int i=1;i<=n;i++) cout<<f[i].count()<<endl; }