比较基础的题目
首先边肯定是要反着加的
然后可以用tarjan一次求出来所有的scc
这个也就是缩点
然后看有几个点入度是0
这个点指得是强连通分量
如果入度为0 的点只有一个就直接把这个点的点数输出
否则输0
没了
#include#include #include #include #include #define MAX 50009 #define rep(i,j,k) for(int i = j; i <= k; i++) using namespace std; int to[2 * MAX], next[2 * MAX], head[MAX]; int SccNum = 0, DfsClock = 0, dfn[MAX], low[MAX], num[MAX], In[MAX], in[MAX]; int tot = 0, scc[MAX], n, m; stack s; inline void add (int x, int y) { to[++tot] = y; next[tot] = head[x]; head[x] = tot; } void tarjan (int x) { dfn[x] = low[x] = ++DfsClock; in[x] = 1; s.push (x); for (int i = head[x]; i; i = next[i]) if (!dfn[to[i]]) { tarjan (to[i]); low[x] = min (low[x], low[to[i]]); } else if (in[to[i]]) low[x] = min (low[x], dfn[to[i]]); if (low[x] == dfn[x]) { SccNum++; while (1) { num[SccNum]++; int now = s.top(); s.pop (); in[now] = 0; scc[now] = SccNum; if (now == x) break; } } } int main() { scanf ("%d%d", &n, &m); rep (i, 1, m) { int a1, a2; scanf ("%d%d", &a1, &a2); add (a2, a1); } rep (i, 1, n) if (!dfn[i]) tarjan (i); rep (i, 1, n) for (int j = head[i]; j; j = next[j]) if (scc[i] != scc[to[j]]) In[scc[to[j]]]++; // rep (i, 1, SccNum) // printf ("%d-- %d\n", i, num[i]); int ans = 0, u = 0; rep (i, 1, SccNum) if (!In[i]) ans = num[i], u++; if (u == 1) printf ("%d\n", ans); else printf ("0\n"); return 0; }