[ZJOI2012]灾难

图论 拓扑排序

题面

戳我

解析

一道挺不错的图论题。

$50pts$算法

模拟。
$O(n^2)$暴力随便秒。
咕谷上居然有$70pts$。

il void dfs(re int u)
{
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(!--g[v]) ++ans,dfs(v);
    }
}
int main()
{
  memset(h,-1,sizeof(h));
  n=gi();
  fp(i,1,n)
    {
      re int x=gi();
      while(x)
    {
      add(x,i);++d[i];
      x=gi();
    }
    }
  fp(i,1,n)
    {
      fp(j,1,n) g[j]=d[j];
      ans=0,dfs(i),printf("%d\n",ans);
    }
  return 0;
}

$100pts$算法

一个点灭绝，要求其所有入度灭绝。
它所有入度灭绝，要求它所有入度的$lca$灭绝。
这样，就说明这个点对$lca$的灾难值有贡献。

比较容易想到的$idea$，但这样复杂度还是$O(n^2)$。
考虑到如果一个点$u$单独对$lca$有贡献，那么所有对它有贡献的点也对$lca$有贡献。
这种关系实际为$lca$包含$u$，可以用树形结构中的父子关系体现。

于是我们可以依此关系重建树。
想想这是一张有向无环图，八成考拓扑排序。
那么就按拓扑序建树，每个点的父亲就是它所有入度点的$lca$。

$lca$必须用倍增求，因为这是动态维护信息。
$t[0]$存原图，$t[1]$存反图，$t[2]$存树。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e5+100;
int n,d[N],ans[N],sta[N],top,f[17][N],deep[N];
struct graph
{
  int h[N],cnt;
  struct Edge{int to,nxt;}e[N<<1];
  il graph(){memset(h,-1,sizeof(h));}
  il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
}t[3];
queue<int>Q;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void Toposort()
{
  fp(i,1,n) if(!d[i]) Q.push(i);
  while(!Q.empty())
    {
      re int u=Q.front();Q.pop();sta[++top]=u;
      for(re int i=t[0].h[u];i+1;i=t[0].e[i].nxt)
    {
      re int v=t[0].e[i].to;
      if(!--d[v]) Q.push(v);
    }
    }
}
il int getlca(re int u,re int v)
{
  if(deep[u]<deep[v]) swap(u,v);
  fq(i,16,0) if(deep[f[i][u]]>=deep[v]) u=f[i][u];
  if(u==v) return u;
  fq(i,16,0) if(f[i][u]^f[i][v]) u=f[i][u],v=f[i][v];
  return f[0][u];
}
il void dfs(re int u)
{
  for(re int i=t[2].h[u];i+1;i=t[2].e[i].nxt)
    {
      re int v=t[2].e[i].to;
      dfs(v);
      ans[u]+=ans[v];
    }
  ++ans[u];
}
int main()
{
  n=gi();
  fp(i,1,n)
    {
      re int x=gi();
      while(x)
      {
        t[0].add(x,i);t[1].add(i,x);++d[i];x=gi();
      }
    }
  Toposort();
  fp(i,1,n)
    {
      re int u=sta[i],lca=-1;
      for(re int j=t[1].h[u];j+1;j=t[1].e[j].nxt)
    {
      re int v=t[1].e[j].to;
      if(lca==-1) lca=v;else lca=getlca(lca,v);
    }
      if(lca==-1) lca=0;
      t[2].add(lca,u);
      deep[u]=deep[lca]+1;
      f[0][u]=lca;
      fp(j,1,16) f[j][u]=f[j-1][f[j-1][u]];
    }
  dfs(0);
  fp(i,1,n) printf("%d\n",ans[i]-1);
  return 0;
}