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

可达性统计 拓扑+状态压缩(bitset)

程序员文章站 2022-07-12 16:43:31
...

牛客

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
题目描述
给定一张N个点M条边的有向无环图,分别统计从每个点出发能够到达的点的数量。N,M≤30000N,M \leq 30000N,M≤30000。
输入描述:

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

输出描述:

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

示例1
输入
复制

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
//拓扑排序任意一条边(x,y) x都排在y之前 ->考虑拓扑排序的倒序

#include<bits/stdc++.h>
using namespace std;
const int N=30010;
vector<int>v[N];int deg[N],n,tot[N],a[N],cnt;
bitset <N> s[N];
void topsort()
{
	queue<int >q;
	for(int i=1;i<=n;i++)
	{
		if(deg[i]==0) q.push(i);
	}
	while(q.size())
	{
		int x=q.front();q.pop();
		a[++cnt]=x;
		for(int i=0;i<v[x].size();i++)
		{
			int y=v[x][i];if(--deg[y]==0) q.push(y);
		}
	}
} 
int main()
{
	int m;scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b;scanf("%d%d",&a,&b);
		v[a].push_back(b);deg[b]++;//入度
	}
	topsort();
	for(int i=cnt;i>=1;i--)
	{
		int x=a[i];
		s[x][x]=1;  //s[i][j] =1 表示点i可以到达j点
		for(int j=0;j<v[a[i]].size();j++)
		{
			s[x]|=s[v[x][j]];
		}
	}
	for(int i=1;i<=n;i++) printf("%d\n",s[i].count());
}