写法一主要是拓扑排序用dfs写

写法二直接在DAG图上dp, 不需要拓扑排序

容易想错的点是, 定义状态dp[u]为从结点u出发能够遍历的点的个数. 这样定义的状态可能会重复统计一些点, 举例来说

1 –> 2, 1 –> 3, 2 –> 4, 3 –> 4

这样dp[2] = 2, dp[3] = 2, 对于结点1, 它由结点2和结点3转移过来, dp[1] = 1 + dp[2] + dp[3] = 5, 这里这样就错了, 因为对于结点4它被结点1统计了两次.

所以dp[u]定义为从结点u出发能够遍历的点的集合(而不是个数),转移的时候取并集, 就不同统计重复的点了.

多说一点, 对于所有的dp, 如果我们把状态的定义看成图上的一个结点, 状态的转移看成图上的边, 那么这个图就是一个DAG图. 所以对于DAG图, 我们可以直接dp, 就像本题一样, 可以省去拓扑排序这一步

写法一

#include <bits/stdc++.h>

const int N = 3e4 + 5;
int n, m, vis[N];
std::vector<int> sons[N], ans;

std::bitset<N> dp[N];
// 完成以结点u的拓扑排序
void dfs(int u) {
  vis[u] = 1;
  int len = sons[u].size() - 1;
  for (int i = 0; i <= len; ++i) {
    int v = sons[u][i];
    if (!vis[v]) dfs(v);
  }
  ans.push_back(u);
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int u, v;
    scanf("%d %d", &u, &v);
    sons[u].push_back(v);
  }
  for (int i = 1; i <= n; ++i) {
    if (!vis[i]) dfs(i);
  }
  std::reverse(ans.begin(), ans.end());
  // 倒着dp, dp[x]维护从x结点出发能访问到的所有结点的集合
  for (int i = n - 1; i >= 0; --i) {
    int x = ans[i];
    int len = sons[x].size();
    dp[x][x] = 1;
    for (int k = 0; k < len; ++k) {
      int v = sons[x][k];
      dp[x] |= dp[v];
    }
  }
  for (int i = 1; i <= n; ++i) {
    printf("%d\n", dp[i].count());
  }
  return 0;
}

写法二

#include <bits/stdc++.h>

const int N = 3e4 + 5;
int n, m;
bool vis[N];
std::set<int> sons[N];
std::bitset<N> dp[N];

// 从结点u出发能够遍历到的所有点的集合
std::bitset<N> dfs(int u) {
  // 记忆化
  if (vis[u]) return dp[u];

  vis[u] = true;
  dp[u][u] = 1;
  for (auto &v: sons[u]) {
    dp[u] |= dfs(v);
  }
  return dp[u];
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int u, v;
    scanf("%d %d", &u, &v);
    // 去掉自环
    if (u == v) continue;
    sons[u].insert(v);
  }
  for (int i = 1; i <= n; ++i) {
    printf("%d\n", dfs(i).count());
  }
  return 0;
}