可达性统计【拓扑排序】

题目大意:给定一张N个点M条边的有向无环图,分别统计从每个点出发能够到达的点的数量。

思路:
从x出发能够到达的点构成的集合f(x)f(x)f(x)
f(x)=f(x)=f(x)= {x} f(y)\cup{f(y)}∪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的个数 
}
上一篇:过山车 HDU - 2063


下一篇:双指针,BFS和图论(三)