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

CH 2101 可达性统计 拓扑排序+bitset

程序员文章站 2022-07-12 16:39:37
...

描述

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

有一种很显然的思路,就是 num[u]=num[v]+1 v为u的子节点,但是当是 1 2,1 3,2 4,3 4,这几个边的时候,答案就错了,那么怎么解决呢,可以用bitset, 当u 第v位为1,表示u可以到达v,num[u]|=num[v] ,num[u]中1的个数就是可以到达的点的个数,这样就可以解决上面那个案例了

当然,我们要求u,必须要先知道v的二进制数,那么就要先求v,可以先计算这个图的拓扑序,倒着求每个节点 的二进制数就行了;

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstdlib>
#include<deque>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int len=3e4+10;
const ll mod=100003;
int head[len*2],ver[len*2],nex[len*2];
int in[len];
int tot,n,m;
vector<int>tp;
queue<int>qu;
bitset<len>bi[len];
void solve()
{
	for(int i=1;i<=n;++i)
		if(in[i]==0)qu.push(i);
	while(qu.size())
	{
		int u=qu.front();qu.pop();
		tp.push_back(u);
		for(int i=head[u];i;i=nex[i])
		{
			int v=ver[i];
			in[v]--;
			if(in[v]==0)qu.push(v);
		}
	}
}
void add(int u,int v)
{
	tot++;
	ver[tot]=v;
	nex[tot]=head[u];
	head[u]=tot;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;++i)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		in[v]++;
	}
	solve();
	for(int i=tp.size()-1;i>=0;--i)
	{
		int u=tp[i];
		bi[u][u]=1;
		for(int j=head[u];j;j=nex[j])
		{
			int v=ver[j];
			bi[u]|=bi[v];
		}
	}
	for(int i=1;i<=n;++i)
		printf("%d\n",bi[i].count());
}

拓扑排序的一个小总结:

1:可以判断一个图有无环

2:求拓扑序,(优先级)