标签：Tarjan缩点，bfs
题目
给定一些自动机，如果某个自动机A能产生的所有串都能在自动机B中产生，则称B是A的一个升级，求最长链
\[n\leq 50\]分析
两两连边，tarjan缩点求最长链
bfs判断A的所有串能否都在B中产生
具体分析参考PoPoQQQ大爷
code
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//**********head by yjjr**********
const int maxn=66;
bool flag;
int S,n,m,a,b,last[maxn],last2[maxn],tim=0,scc=0,top=0,cnt=0,cnt2=0;
int dfn[maxn],low[maxn],que[maxn],bl[maxn],val[maxn],ans[maxn];
bool inque[maxn],mark[maxn][maxn];
struct data{int a[maxn][2];bool danger[maxn];}T[maxn];
struct edge{int from,to,next;}e[100006],e2[100006];
void insert(int u,int v){e[++cnt]=(edge){u,v,last[u]};last[u]=cnt;}
void insert2(int u,int v){
if(u==v)return;
e2[++cnt2]=(edge){u,v,last2[u]};last2[u]=cnt2;
}
void dfs(int x,int y){
if(flag)return;
if(mark[x][y])return;mark[x][y]=1;
if(T[b].danger[y]&&!T[a].danger[x]){flag=1;return;}
dfs(T[a].a[x][0],T[b].a[y][0]);
dfs(T[a].a[x][1],T[b].a[y][1]);
}
inline bool check(){
flag=0;
mem(mark,0);
dfs(1,1);
return !flag;
}
void tarjan(int x){
dfn[x]=low[x]=++tim;
que[++top]=x;inque[x]=1;
reg(x){
int v=e[i].to;
if(!dfn[v])tarjan(v),low[x]=min(low[x],low[v]);
else if(inque[v])low[x]=min(low[x],dfn[v]);
}
if(low[x]==dfn[x]){
int now=-1;scc++;
while(now!=x){
now=que[top--];inque[now]=0;
bl[now]=scc;val[scc]++;
}
}
}
inline int dfs(int x){
#define reg2(x) for(int i=last2[x];i;i=e2[i].next)
if(ans[x])return ans[x];
ans[x]=val[x];
reg2(x)ans[x]=max(ans[x],dfs(e2[i].to)+val[x]);
return ans[x];
}
int main()
{
S=read();
rep(i,1,S){
n=read(),m=read();
while(m--)T[i].danger[read()+1]=1;
rep(j,1,n)T[i].a[j][0]=read()+1,T[i].a[j][1]=read()+1;
}
rep(i,1,S)rep(j,1,S)
if(i!=j){
a=i,b=j;
if(check())insert(a,b);
}
rep(i,1,S)if(!dfn[i])tarjan(i);
rep(i,1,cnt)insert2(bl[e[i].from],bl[e[i].to]);
int mx=0;
rep(i,1,scc)mx=max(mx,dfs(i));
cout<<mx<<endl;
return 0;
}
