可达性统计 拓扑+状态压缩(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());
}
上一篇: C++ STL之priority_queue的基本用法
下一篇: RPC框架简单手写