简述一个网站设计的主要步骤,如何查名下是否有注册的公司,网站建设服务宗旨,网络营销推广的目的CH2101 可达性统计 描述 给定一张N个点M条边的有向无环图#xff0c;分别统计从每个点出发能够到达的点的数量。N,M≤30000。 输入格式 第一行两个整数N,M#xff0c;接下来M行每行两个整数x,y#xff0c;表示从x到y的一条有向边。 输出格式 共N行#xff0c;表示每个点能够…CH2101 可达性统计 描述 给定一张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 思路 我们可以利用记忆化搜索对于每个点记录它能到达的点的集合。 至于怎么记录这个集合我们采用bitset bitsetMAXN f[MAXN]; 由于bitset十分省内存30000大小就占用30000bit不用担心炸空间。 还有bitset支持位运算你可以当做一个二进制数来操作也可以当做一个bool数组还支持各种神奇函数十分强大。 bitsetMAXN a, b;
a[1] 1;//当做bool数组~
b[2] 1;
a a | b;//支持位运算~
printf(%llu\n, a.count());//统计1的个数~ 返回值是unsigned long long类型的 搜索过程十分简单差不多是一个记忆化搜索模板。 P.S. 当然你也可以拓扑序DP 代码 #includebits/stdc.h
using namespace std;
#define MAXN 30005
#define MAXM 30005
#define bs bitset30005int n, m;
int hd[MAXN], nxt[MAXM], to[MAXM], tot;
bs f[MAXN];
int x, y;inline void Add( int x, int y ){ nxt[tot] hd[x]; hd[x] tot; to[tot] y; }void DFS( int x ){if ( f[x].any() ) return;f[x][x] 1;for ( int i hd[x]; i; i nxt[i] )f[x] | ( DFS( to[i] ), f[to[i]] );
}int main(){scanf( %d%d, n, m );for ( int i 1; i m; i ){ scanf( %d%d, x, y ); Add( x, y ); }for ( int i 1; i n; i ) printf( %llu\n, ( DFS(i), f[i].count() ) );return 0;
} 转载于:https://www.cnblogs.com/louhancheng/p/10100270.html
