[bzoj1051][HAOI2006]受欢迎的牛——强连通分量

题目大意：

给定一个有向图，求能够被其他所有点访问到的点的个数。

题解：

首先，这个题我在洛谷上AC了，但是bzoj上WA，不知道为什么。

说一下解法。

首先，我们进行scc分解，可以知道，

1. 如果一个点满足条件，那么这个点所在的scc中的所有点都满足条件。
2. 至多只有一个scc满足条件。
3. 满足条件的scc出度为0。

直接使用kosaraju算法求解即可。

问题：为什么我在bzoj上会wa？求各位大佬给一组bzoj版本数据QAQ

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 10010;

int n, m;

vector<int> G[maxn];

vector<int> rG[maxn];

vector<int> sc[maxn];

int cnt[maxn];

vector<int> vs;

bool vis[maxn];

void dfs(int v) {

  vis[v] = true;

  for (int i = 0; i < G[v].size(); i++) {

    if (!vis[G[v][i]])

      dfs(G[v][i]);

  }

  vs.push_back(v);

}

void rdfs(int v, int k) {

  vis[v] = true;

  cnt[v] = k;

  for (int i = 0; i < rG[v].size(); i++) {

    if (!vis[rG[v][i]])

      rdfs(rG[v][i], k);

  }

  vs.push_back(v);

  sc[k].push_back(v);

}

int scc() {

  memset(vis, 0, sizeof(vis));

  vs.clear();

  for (int v = 1; v <= n; v++) {

    if (!vis[v])

      dfs(v);

  }

  memset(vis, 0, sizeof(vis));

  int k = 0;

  for (int i = vs.size() - 1; i >= 0; i--) {

    if (!vis[vs[i]]) {

      rdfs(vs[i], k++);

    }

  }

  return k;

}

void dfs2(int k) {

  vis[k] = 1;

  for (int i = 0; i < rG[k].size(); i++)

    if (!vis[rG[k][i]])

      dfs2(rG[k][i]);

}

bool check(int i) {

  memset(vis, 0, sizeof(vis));

  dfs2(i);

  for (int i = 1; i <= n; i++)

    if (!vis[i])

      return 0;

  return 1;

}

int main() {

  // freopen("input", "r", stdin);

  scanf("%d %d", &n, &m);

  for (int i = 1; i <= m; i++) {

    int a, b;

    scanf("%d %d", &a, &b);

    G[a].push_back(b);

    rG[b].push_back(a);

  }

  int k = scc();

  k--;

  if (check(sc[k][0])) {

    printf("%lld\n", sc[k].size());

  } else {

    printf("%lld\n", 0);

  }

  return 0;

}