AC_NOIP_AK_IOI @ 2023-02-05 16:07:47
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,f[1001],in[1001],b[1001],maxn;
bool flag[1001];
vector<int> adj[1001];
queue<int> q;
void bfs()
{
while(!q.empty())
{
int t=q.front();
q.pop();
for(int i=0;i<adj[t].size();i++)
{
int x=adj[t][i];
f[x]=max(f[x],f[t]+1);
in[x]--;
if(in[x]==0)q.push(x);
}
}
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x;
cin>>x;
memset(flag,0,sizeof(flag));
for(int j=1;j<=x;j++)
{
cin>>b[j];
flag[b[j]]=1;
}
for(int j=b[1];j<=b[x];j++)
{
if(!flag[j])
{
for(int k=1;k<=x;k++)
{
if(!count(adj[j].begin(),adj[j].end(),b[k])) //这个指令是看adj[j]数组里有没有b[k]这个元素
{
adj[j].push_back(b[k]);
in[b[k]]++;
}
}
}
}
}
for(int i=1;i<=n;i++)
{
if(in[i]==0)f[i]=1,q.push(i);
}
bfs();
for(int i=1;i<=n;i++)maxn=max(maxn,f[i]);
cout<<maxn;
return 0;
}
最后三个点TLE。QAQ
by YJM_yejiaming @ 2023-02-05 16:13:04
dfs中TLE百分之八九十是没记忆化搜索
by AC_NOIP_AK_IOI @ 2023-02-05 16:38:40
@YJM_yejiaming,我是bfs。
by AC_NOIP_AK_IOI @ 2023-02-09 20:38:27
此题已AC!此贴终结!