题目链接：
题解：
强连通缩点得到DAG图，将图转置一下，对入度为零的点跑dfs看看能不能访问到所有的点。
代码：
#include#include #include #include #include #include using namespace std;const int maxn = 10000 + 10;const int INF = 0x3f3f3f3f;vector G[maxn],G2[maxn];int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;int ind[maxn],siz[maxn],vis[maxn];stack S;int n,m;void dfs(int u) { pre[u] = lowlink[u] = ++dfs_clock; S.push(u); for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if (!pre[v]) { dfs(v); lowlink[u] = min(lowlink[u], lowlink[v]); } else if (!sccno[v]) { lowlink[u] = min(lowlink[u], pre[v]); } } if (lowlink[u] == pre[u]) { scc_cnt++; int cnt = 0; for (;;) { cnt++; int x = S.top(); S.pop(); sccno[x] = scc_cnt; if (x == u) break; } siz[scc_cnt] = cnt; }}void find_scc(int n) { dfs_clock = scc_cnt = 0; memset(sccno, 0, sizeof(sccno)); memset(pre, 0, sizeof(pre)); for (int i = 0; i < n; i++) if (!pre[i]) dfs(i); //for (int i = 0; i < n; i++) printf("sccno[%d]:%d\n", i, sccno[i]);}void dfs2(int u) { if (vis[u]) return; vis[u] = 1; for (int i = 0; i < G2[u].size(); i++) { int v = G2[u][i]; dfs2(v); }}void init() { for (int i = 0; i < n; i++) G[i].clear(), G2[i].clear(); memset(ind, 0,sizeof(ind)); memset(vis, 0, sizeof(vis));}int main() { while (scanf("%d%d", &n,&m) == 2 && n) { init(); for (int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); u--, v--; G[u].push_back(v); } find_scc(n); for (int i = 0; i < n; i++) { for (int j = 0; j < G[i].size(); j++) { int v = G[i][j]; if (sccno[i] != sccno[v]) { G2[sccno[v]].push_back(sccno[i]); ind[sccno[i]]++; } } } int rt = -1; for (int i = 1; i <= scc_cnt; i++) { if (ind[i] == 0) rt = i; } dfs2(rt); int su = 1; for (int i = 1; i <= scc_cnt; i++) { if (!vis[i]) { su = 0; break; } } if (su) { printf("%d\n", siz[rt]); } else { printf("0\n"); } } return 0;}