upc 可达性统计 （拓扑排序+bitset）

题目描述

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

 

输入

第一行两个整数N,M，接下来M行每行两个整数x,y，表示从x到y的一条有向边。

 

输出

共N行，表示每个点能够到达的点的数量。

 

样例输入

10 10
3 8
2 3
2 5
5 9
5 9
2 3
3 9
4 8
2 10
4 9

样例输出

1
6
3
3
2
1
1
1
1
1

此题暴力统计每个点的话，超时！经过一番百度，get到了拓扑排序这个算法，以及bitset这个神奇的库

拓扑排序是一种对点进行排序的算法，如果有一条有向边u->v，那么在排好序的点的序列中，v一定在u的后面。

简述：

先找入度为零的点，加入数组，以它为起点，剪去以它作为起点的边，再找入度为零的点，加入数组，最后的到一个点的序列

再说一下这个bitset库  bitset<30005>a[30005] 可以说开了以“数组”叫a，大小是30005，一个数据类型存储30005位，

排好序后，从后往前，因为后面的数能到达的点一般情况下是比前面的点少的，用后面的点去更新前面的点

上代码吧：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector> 
#include<bitset>
using namespace std;
const int inf=0x7f;
const int maxn=30000+10;
const int maxm=30000+10;
int n,m,x,y,k,ans,ind[maxn],vis[maxn],head[maxm];
vector<int> v;
bitset<maxn> a[maxn];
struct Edge
{
	int before;
	int to;
}e[maxm];
void add(int u,int v)
{
	e[k].before=head[u];
	e[k].to=v;
	head[u]=k++;	
}
void init()
{
	k=0;
	memset(vis,0,sizeof vis);
	memset(head,-1,sizeof head);
	memset(ind,0,sizeof ind);
}
void bfs(int s)
{
	queue<int> q;
	q.push(s);
	vis[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		v.push_back(u);
		for(int i=head[u];i!=-1;i=e[i].before)
		{
			int v=e[i].to;
			ind[v]--;
			if(ind[v]==0&&vis[v]==0)
			{
				vis[v]=1;
				q.push(v);
			}
		}
	}
}
void tsort()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=head[i];j!=-1;j=e[j].before)
		ind[e[j].to]++;	
	}
	for(int i=1;i<=n;i++)
	{
		if(vis[i]==0&&ind[i]==0)
		bfs(i);
	}
}
int main()
{
//	freopen("in.txt","r",stdin);
	scanf("%d %d",&n,&m);
	init();
	for(int i=0;i<m;i++)
	{
		scanf("%d %d",&x,&y);
		add(x,y);	
	}
	tsort();
	for(int i=v.size()-1;i>=0;i--)
	{
		int x=v[i];
		a[x][x]=1;
		for(int j=head[x];j!=-1;j=e[j].before)
		a[x]=a[x]|a[e[j].to]; 
	}	 
	for(int i=1;i<=n;i++)
	printf("%lld\n",a[i].count());
	return 0;
}