题目描述：
给定一张 $N$ 个点 $M$ 条边的有向无环图，分别统计从每个点出发能够到达的点的数量。
数据范围：
$1\le N,M \le 3\times 10^4; 1\le x,y\le N$
题解：
如果 $u\rightarrow v$，则可以得到 $dp[u] = dp[u] \cup dp[v]$。需要从最后一个点往前dp。
使用状态压缩，用一串二进制数表示可以到达哪些节点。可以使用 $bitset$。
总体复杂度为 $O(\frac{N(N + M)}{32})$。所以只能过 $10^4$ 范围左右的，$10^5$ 超时。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 3e4 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
vector<int> g[maxn];
int indeg[maxn];
int nums[maxn];
int cnt = 0;
bitset<maxn> dp[maxn];
void topoSort()
{
queue<int> q;
for (int i = 1; i <= n; ++i)
{
if (!indeg[i])
q.push(i);
}
while (q.size())
{
int u = q.front();
q.pop();
nums[++cnt] = u;
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i];
indeg[v]--;
if (!indeg[v])
{
q.push(v);
}
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
read(n, m);
for (int i = 0, u, v; i < m; ++i)
{
read(u, v);
indeg[v]++;
g[u].emplace_back(v);
}
topoSort();
for (int i = n; i >= 1; --i)
{
int u = nums[i];
dp[u][u] = 1;
for (int j = 0; j < g[u].size(); ++j)
{
int v = g[u][j];
dp[u] |= dp[v];
}
}
for (int i = 1; i <= n; ++i)
{
cout << dp[i].count() << endl;
}
return 0;
}
|