問題模型：
在一張捕食圖上（從捕食者向被捕食者有連邊），若某生物的所有食物都滅絕了，則該生物滅絕。
滅絕樹便是此圖的一種生成樹，使得滿足滅絕樹上某點滅絕，該點子樹内所有點都滅絕
支配樹，就是滿足樹上一個點xx的所有祖先都是它的支配點的樹。
一、樹形圖
樹形圖就是自己的支配樹
二、DAG
對于DAG，先拓撲排序，再建樹，建樹的時候順便把倍增數組處理一下，最後dfs統計一下。
建樹過程：假設i的食物有x[0]…x[k]（x[0]…x[k]在拓撲排序中比i靠前），
很顯然，隻有x[0]~x[k]在樹上的公共祖先的滅絕會導緻i滅絕，否則i一定可以找到能讓它活下來的食物。
于是，我們可以把i挂在x[0]~x[k]的最近公共祖先下面。
處理完所有的生物，我們得到的樹就是整個圖的滅絕樹了。之後dfs計算一下每個節點對應的子樹大小，子樹大小-1即危險程度
#include <bits/stdc++.h>
#define sz 31
using namespace std;
const int maxn = 65540;
const int maxm = 1e6+100;
int cnt,nxt[maxm<<1],fst[maxn],to[maxm<<1];
int cnt1,nxt1[maxm<<1],fst1[maxn],to1[maxm<<1];
int cnt2,nxt2[maxm<<1],fst2[maxn],to2[maxm<<1];
int n,in[maxn],ran[maxn],h[maxn],f[maxn][sz],ans[maxn];
void addedge(int u,int v){
to[++cnt] = v;
nxt[cnt] = fst[u];
fst[u] = cnt;
}
void addedge1(int u,int v){
to1[++cnt1] = v;
nxt1[cnt1] = fst1[u];
fst1[u] = cnt1;
}
void addedge2(int u,int v){
to2[++cnt2] = v;
nxt2[cnt2] = fst2[u];
fst2[u] = cnt2;
}
void topsort(){
queue <int> q;
for (int i=1;i<=n;i++)
if (!in[i]) q.push(i);
int num = 0;
while(!q.empty()){
int now = q.front();
q.pop();
ran[++num] = now;
for (int i = fst[now];i;i=nxt[i]){
in[to[i]]--;
if(!in[to[i]]) q.push(to[i]);
}
}
}
int lca(int x,int y){
if (h[x]<h[y]) swap(x,y);
int k = h[x] - h[y];
for (int i = 0;i<sz;i++)
if ((k>>i)&1) x=f[x][i];
if(x == y)return x;
for (int i=sz-1;i>=0;i--)
if (f[x][i] != f[y][i])
x = f[x][i],y = f[y][i];
return f[x][0];
}
void dfs(int now){
for (int i=fst2[now];i;i=nxt2[i]){
dfs(to2[i]);
ans[now] += ans[to2[i]];
}
ans[now]++;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i=1;i<=n;i++){//addedge是反的
int x;
cin >> x;
while (x) {
in[i]++;
addedge(x,i);
addedge1(i,x);
cin >> x;
}
}
topsort();
for (int i =1;i<=n;i++){
int x = to1[fst1[ran[i]]];
for (int j = fst1[ran[i]];j;j = nxt1[j])
x = lca(x,to1[j]);
//the LCA of every suffix node of ran[i]
addedge2(x,ran[i]);
h[ran[i]] = h[x] +1;
f[ran[i]][0] = x;
for (int j=1;j<sz;j++)
f[ran[i]][j] = f[f[ran[i]][j-1]][j-1];
}
dfs(0);
for (int i=1;i<=n;i++)
cout << ans[i]-1 <<endl;
}
三、一般圖
L e n g a u e r − T a r j a n Lengauer−Tarjan Lengauer−Tarjan算法
洛谷闆子題解
#include <bits/stdc++.h>
#define N 500008
#define IL inline
#define M 1008611
#define R register
using namespace std;
template<typename T>void read(T &a)
{
T x=0,f=1;char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')f=0;ch=getchar();
}
while(isdigit(ch))
{
x=(x<<1)+(x<<3)+ch-'0';ch=getchar();
}
a=f?x:-x;
}
/*-------------OI使我快樂-------------*/
int n,m,tot,cnt;
int head[M<<1],pre[N<<1],to[N<<2],nex[N<<2],lat[M],cdy[M];
int bel[M],val[M],sdom[M],idom[M],ans[M];
int dfn[M],id[M],fa[M];
IL void add(int *h,int x,int y)
{to[++tot]=y;nex[tot]=h[x];h[x]=tot;}
IL void dfs(int now)
{
dfn[now]=++cnt;id[cnt]=now;
for(R int i=head[now];i;i=nex[i])
{
int v=to[i];
// printf("%d --> %d\n",now,v);
if(dfn[v]) continue;
dfs(v);fa[v]=now;
}
}
IL int find(int x)
{
if(x==bel[x]) return x;
int root=find(bel[x]);
if(dfn[sdom[val[bel[x]]]]<dfn[sdom[val[x]]])
val[x]=val[bel[x]];
return bel[x]=root;
}
IL void Tarjan()
{
// for(R int i=1;i<=n;++i) printf("dfn[%d] %d\n",i,dfn[i]);
for(R int i=cnt;i>=2;--i)
{
int now=id[i];
//我們按照dfs序 從大到小處理 節點
for(R int j=pre[now];j;j=nex[j])
{//這裡用鍊式前向星 存入度節點
int v=to[j];
if(!dfn[v]) continue;
find(v);
//dfn[y]<dfn[x]的話
//我們還未處理到 sdom[y]=val[y]=y
//此時y的并查集樹中隻有TA自己 更新是合法的
//dfn[y]>dfn[x]的話
//就按照套路比較
if(dfn[sdom[val[v]]]<dfn[sdom[now]])
sdom[now]=sdom[val[v]];
}
add(lat,sdom[now],now);
bel[now]=fa[now];
//同其在dfs樹上的父親連邊
now=fa[now];
//現在父親到TA這棵子樹已經處理完了
//是以此時我們可以對
//以父親為sdom[x]的x分别求一次sdom 然後清空
//對于每一個點進行更新
for(R int j=lat[now];j;j=nex[j])
{
int v=to[j];
find(v);
if(sdom[val[v]]==now) idom[v]=now;
//如果sdom[z]==sdom[x] 那麼idom[x]=sdom[x]
//此時sdom[x]=now
else idom[v]=val[v];
//否則就是idom[x]=idom[z]
//但是實際實作我們可以寫成idom[x]=z
//然後在接下來處理
}
}
for(R int i=2,now;i<=cnt;++i)
{
now=id[i];
if(idom[now]!=sdom[now]) idom[now]=idom[idom[now]];
//這是殘餘節點的填坑大作戰
}
}
IL void dfs_ans(int now)
{
ans[now]=1;
for(R int i=cdy[now];i;i=nex[i])
{
int v=to[i];
dfs_ans(v);
ans[now]+=ans[v];
}
}
int main()
{
read(n);read(m);
for(R int i=1,x,y;i<=m;++i)
{
read(x);read(y);
add(head,x,y);add(pre,y,x);
}
for(R int i=1;i<=n;++i)
sdom[i]=bel[i]=val[i]=i;
dfs(1);
Tarjan();
// puts("How old are you ? ");
// for(int i=1;i<=n;++i)
// {
// printf("支配點[%d] %d\n",i,idom[i]);
// }
tot=0;
for(R int i=2;i<=n;++i) if(idom[i]) add(cdy,idom[i],i);
dfs_ans(1);
for(R int i=1;i<=n;++i) printf("%d%c",ans[i],(i==n ? '\n':' '));
return 0;
}