BZOJ 2815。
解法还是挺巧妙的。
放上写得很详细很好懂的题解链接 戳这里。
一个物种$x$如果要灭绝，那么沿着它的入边反向走走走，一定可以走到一个点$y$，如果这个点$y$的物种灭绝了，那么$x$也一定会灭绝。而且，因为一次只能灭绝一个物种，只有满足这个条件这个物种$x$才会灭绝。
那么我们可以考虑建立一棵树，对于一个点$x$，将它能直接导致灭绝的点$y$作为它的直接儿子，然后我们统计一下每一个结点的$siz$再$- 1$就是答案了。
考虑一下如何找到这个走走走之后的关键点，因为这张图满足$DAG$的性质，我们可以一边拓扑排序一边建树，如果当前从队列里面取出了$x$，那么所有在$x$之前能走到的点一定在我们建的树里面了，我们只要在建好的树上找到所有直接连通$x$的点的$lca$作$x$的父亲就可以了。
插点的倍增$lca$，可以直接动态维护出来。
可以建一个超级源点连通所有的连通块。
时间复杂度$O(nlogn)$。
Code：
#include <cstdio> #include <cstring> #include <vector> using namespace std; const int N = 1e5 + 5; const int Lg = 20; int n, rt, tot = 0, head[N]; int q[N], fa[N][Lg], dep[N], deg[N], siz[N]; vector <int> G1[N], G2[N]; struct Edge { int to, nxt; } e[N << 1]; inline void add(int from, int to) { e[++tot].to = to; e[tot].nxt = head[from]; head[from] = tot; } inline void read(int &X) { X = 0; char ch = 0; int op = 1; for(; ch > ‘9‘ || ch < ‘0‘; ch = getchar()) if(ch == ‘-‘) op = -1; for(; ch >= ‘0‘ && ch <= ‘9‘; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op; } inline void swap(int &x, int &y) { int t = x; x = y; y = t; } inline void prework(int x, int fat) { dep[x] = dep[fat] + 1, fa[x][0] = fat; for(int i = 1; i <= 18; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1]; } inline int getLca(int x, int y) { if(dep[x] < dep[y]) swap(x, y); for(int i = 18; i >= 0; i--) if(dep[fa[x][i]] >= dep[y]) x = fa[x][i]; if(x == y) return x; for(int i = 18; i >= 0; i--) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i]; return fa[x][0]; } inline void topSort() { int l = 0, r = 1; q[1] = rt; prework(rt, 0); for(; l <= r; ) { int x = q[++l], fat = 0, vecSiz = G2[x].size(); for(int i = 0; i < vecSiz; i++) { int y = G2[x][i]; if(!fat) fat = y; else fat = getLca(fat, y); } if(x != rt) add(x, fat), add(fat, x); prework(x, fat); vecSiz = G1[x].size(); for(int i = 0; i < vecSiz; i++) { int y = G1[x][i]; --deg[y]; if(!deg[y]) q[++r] = y; } } } void dfs(int x, int fat) { siz[x] = 1; for(int i = head[x]; i; i = e[i].nxt) { int y = e[i].to; if(y == fat) continue; dfs(y, x); siz[x] += siz[y]; } } int main() { read(n); for(int x, i = 1; i <= n; i++) { for(read(x); x; read(x)) { G1[x].push_back(i); G2[i].push_back(x); ++deg[i]; } } rt = n + 1; for(int i = 1; i <= n; i++) if(!deg[i]) { G1[rt].push_back(i); G2[i].push_back(rt); ++deg[i]; } topSort(); dfs(rt, 0); for(int i = 1; i <= n; i++) printf("%d\n", siz[i] - 1); return 0; }
原文：https://www.cnblogs.com/CzxingcHen/p/9863063.html
