题目描述
给定一张N个点M条边的有向无环图,分别统计从每个点出发能够到达的点的数量。
样例
输入样例:
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
算法1
(搜索+拓扑排序+bitset)
题目给的是有向无环图,所以是一个点接着一个点的。
可以对点进行拓扑排序,然后令f[i]
为点i
可以到达的点的数量。
然后需要考虑f[i]
用什么变量取存储的问题。
因为题目给了$30000$个点,如果用int
变量来存的话。最坏的情况下,拓扑排序后会形成一个链表。
总共需要往容器里push
$n^2 / 2$个点,因为一个int
有32位数,假设用int
去记录可到达点的情况,1
表示可以到达,0
表示不能到达。$30000 * \frac{30000}{2 * 32} ~= 3x10^7$,\ $10^6$个int
~= 4M, $3 x 10^7 = 120M$ 完全ok(题目给了256M)。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <bitset>
#include <queue>
#include <cstring>
using namespace std;
const int N = 30010;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N], seq[N];
bitset<N> f[N];
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void topsort(){
queue<int> q;
for (int i = 1; i <= n; i ++)
if (!d[i])
q.push(i);
int k = 0;
while (q.size()){
int t = q.front();
q.pop();
seq[k ++] = t;
for (int i = h[t]; ~i; i = ne[i]){
int j = e[i];
if (-- d[j] == 0)
q.push(j);
}
}
}
int main(){
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++){
int a, b;
cin >> a >> b;
add(a, b);
d[b] ++;//如果有点到达b,则b的入度+1
}
topsort();
for (int i = n - 1; i >= 0; i --){
int j = seq[i];
f[j][j] = 1;
for (int k = h[j]; ~k; k = ne[k])
f[j] |= f[e[k]];
}
for (int i = 1; i <= n; i ++) cout << f[i].count() << endl;
return 0;
}