# 洛谷2321 [hnoi2006]潘多拉的宝盒

## tarjan缩点求最长链

Posted by yjjr's blog on October 31, 2018

# 分析

bfs判断A的所有串能否都在B中产生

blog

# 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;
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;
}
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()
{
rep(i,1,S){
}
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;
}