大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
给定一张 N 个点 M 条边的有向无环图，分别统计从每个点出发能够到达的点的数量。
输入格式
第一行两个整数 N,M，接下来 M 行每行两个整数 x,y，表示从 x 到 y 的一条有向边。
输出格式
输出共 N 行，表示每个点能够到达的点的数量。
数据范围
1≤N,M≤30000
输入样例：
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
#include<bits/stdc++.h>
using namespace std;
const int N = 3e4 + 10;
const int M = 3e4 + 10;
struct Edge{
int v,next;
}edge[M];
int head[N],cnt;
void add(int u,int v){
edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt ++;
}
bitset<N>f[N];
int in[N],q[N],hh = 0,tt = 0;
int main(){
int n,m;
cin>>n>>m;
int x,y;
memset(head,-1,sizeof head);
for(int i = 0;i < m;i ++){
cin>>x>>y;
add(x,y),in[y] ++;
}
for(int i = 1;i <= n;i ++)if(!in[i])q[tt ++] = i;
while(hh < tt){
int t = q[hh ++];
for(int i = head[t];~i;i = edge[i].next){
int v = edge[i].v;
if((-- in[v]) == 0)q[tt ++] = v;
}
}
for(int i = tt - 1;i >= 0;i --){
int j = q[i];
f[j][j] = 1;
for(int k = head[j];~k;k = edge[k].next){
int v = edge[k].v;
f[j] |= f[v];
}
}
for(int i = 1;i <= n;i ++){
cout<<f[i].count()<<endl;
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/169088.html原文链接：https://javaforall.net
