链接:
https://www.acwing.com/problem/content/166/
题意:
给定一张 N 个点 M 条边的有向无环图, 分别统计从每个点出发能够到达的点的数量.
思路:
先拓扑排序求出顺序, 再通过 bitset 利用位运算, 记录并集, 可以解决重复计算的问题.
代码:
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 3e4+10;
- vector G[MAXN];
- vector Tup;
- bitset<30010> F[MAXN];
- int Dis[MAXN];
- int n, m;
- void Tupo()
- {
- queue que;
- for (int i = 1;i <= n;i++)
- {
- if (Dis[i] == 0)
- que.push(i);
- }
- while (!que.empty())
- {
- int node = que.front();
- que.pop();
- Tup.push_back(node);
- for (int i = 0;i <G[node].size();i++)
- {
- int to = G[node][i];
- if (--Dis[to] == 0)
- que.push(to);
- }
- }
- }
- void Solve()
- {
- for (int i = n-1;i>= 0;i--)
- {
- int x = Tup[i];
- F[x].reset();
- F[x][x] = 1;
- for (int k = 0;k < G[x].size();k++)
- {
- F[x] |= F[G[x][k]];
- }
- }
- }
- int main()
- {
- scanf("%d%d", &n, &m);
- int u, v;
- for (int i = 1;i <= m;i++)
- {
- scanf("%d%d", &u, &v);
- G[u].push_back(v);
- Dis[v]++;
- }
- Tupo();
- Solve();
- for (int i = 1;i <= n;i++)
- printf("%d\n", (int)F[i].count());
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3201304.html