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:求拓扑序,(优先级)
上一篇: 手写简单RPC实现
下一篇: 【拓扑排序+bitset】可达性统计