[文章目录]
Description
给你一个含有n个元素的集合，每个元素都可以限制另一种元素，选出最大子集使得对于该子集中每个元素都被其补集中另一个元素限制。n<=10^6
基环树DP。被限制元素为父亲，限制元素为儿子。
f[i]表示选i，g[i]表示不选i转移即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 1001000
const int inf=0x3f3f3f3f;
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
x=0; char ch=nc();
while(!isdigit(ch)) ch=nc();
while(isdigit(ch)) x=x*10+ch-'0',ch=nc();
}
int n,fa[N],za[N],zb[N],tot;
int head[N],to[N],nxt[N],cnt;
void add(int x,int y) {to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int f[N],g[N],lim;
void dfs(int x)
{
g[x]=0; int t=-inf;
for(int i=head[x];i;i=nxt[i])
{
if(to[i]!=lim) dfs(to[i]);
g[x]+=max(f[to[i]],g[to[i]]);
t=max(t,g[to[i]]-max(f[to[i]],g[to[i]]));
}
f[x]=g[x]+t+1;
}
int main()
{
read(n);
for(int i=1;i<=n;++i) fa[i]=i;
int x;
for(int i=1;i<=n;++i)
{
read(x);
if(find(x)==find(i)) za[++tot]=i,zb[tot]=x;
else fa[fa[x]]=fa[i],add(x,i);
}
int ans=0,tmp;
for(int i=1;i<=tot;++i)
{
lim=0; dfs(za[i]); tmp=max(f[za[i]],g[za[i]]);
f[zb[i]]=g[zb[i]]+1; g[zb[i]]=-inf; lim=zb[i]; dfs(za[i]);
ans+=max(tmp,g[za[i]]);
}
printf("%d",ans);
return 0;
}