为什么这个算法跑的这么慢

w9095 @ 2023-03-21 19:51:44

by w9095 @ 2023-03-21 19:51:57

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int v,next,dis;
}e[1000010];
int n,m,s,h[1010],cnt=0,z[1010],book[1010],dis[1010],ind[1010],vis[1010][1010],ans=0;
void add_edge(int f,int v,int dis)
{
    e[++cnt].next=h[f];
    e[cnt].v=v;
    e[cnt].dis=dis;
    h[f]=cnt;
    ind[v]++;
}

void topo_sort()
{
    int sta[300000],top=0;
    for(int i=0;i<=n;i++)
        if(ind[i]==0)sta[++top]=i;
    while(top)
        {
            int now=sta[top];
            top--;
            for(int i=h[now];i;i=e[i].next)
                {
                ind[e[i].v]--;dis[e[i].v]=max(dis[e[i].v],dis[now]+e[i].dis);
                if(ind[e[i].v]==0)sta[++top]=e[i].v;
                }
        }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
        {
            scanf("%d",&s);
            for(int j=0;j<s;j++)scanf("%d",&z[j]);
            for(int j=0;j<s;j++)book[z[j]]=1;
            for(int k=0;k<s;k++)
                for(int j=z[0];j<=z[s-1];j++)
                    if(!book[j]&&!vis[j][z[k]])
                       {
                       add_edge(j,z[k],1);
                       vis[j][z[k]]=1;
                       }
            memset(book,0,sizeof(book));
        }
    for(int i=1;i<=n;i++)
        add_edge(0,i,0);
    for(int i=1;i<=n;i++)
        dis[i]=-99999999;
    dis[0]=0;
    topo_sort();
    for(int i=1;i<=n;i++)
        ans=max(ans,dis[i]);
    printf("%d",ans+1);
    return 0;
}