欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

upc 可达性统计 (拓扑排序+bitset)

程序员文章站 2022-07-12 16:38:19
...

题目描述

给定一张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;
}