蒟蒻求助！一组点tie，我寻思我这时间复杂度不是（N+M）吗

190040257a @ 2020-02-15 15:43:10

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue> 
using namespace std;
int read()
{
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
bool w[1004][1004];
struct node
{
    int cen;
    int num;
};
int N,M,ans;
bool sf[1005];
int to[1005][1005];
int cun[1005];
int main()
{
    N=read();
    M=read();
    queue<node>P;
    for(int i=1;i<=M;i++)
    {
        int s;
        memset(sf,0,sizeof(sf));
        s=read();
        int hav[1005];
        for(int j=1;j<=s;j++)
        {
            hav[j]=read();
            sf[hav[j]]=1;
        }
        for(int j=1;j<=s;j++)
        {
            int l=hav[j];
            for(int k=hav[1]+1;k<hav[s];k++)
            {
                if(sf[k]==0)
                {
                    if(w[l][k]==0)
                    {
                        to[l][0]++;
                        to[l][to[l][0]]=k;
                        w[l][k]=1;
                        cun[k]++; 
                    }
                }
            }
        }
    }
    for(int i=1;i<=N;i++)
    {
        if(cun[i]==0)
        {
            node x;
            x.num=i;
            x.cen=1;
            P.push(x);
        }
    }
    while(!P.empty())
    {
        node k=P.front();
        P.pop();
        int x=k.num;
        for(int i=1;i<=to[x][0];i++)
        {
            int s=to[x][i];
            cun[s]--;
            if(cun[s]==0)
            {
                node xx;
                xx.num=s;
                xx.cen=k.cen+1;
                P.push(xx);
                ans=max(ans,xx.cen);
            }
        }
    }
    cout<<ans;
    return 0;
}

by Monkey_Hunter @ 2020-02-15 15:46:51

tie是什么

by 190040257a @ 2020-02-15 15:47:45

自觉没啥问题，就是每次把入度为0的点放入，然后找其能到哪些点，然后减入度，再放入。 按理一个点最多放入队列一次，每条边也最多算一次复杂度不应该是N+M吗？

by michael_song @ 2020-02-15 18:13:14

@190040257a

把数组开大点

有的时候会蜜汁TLE

by 190040257a @ 2020-02-15 18:41:03

@michael_song 貌似没啥效果，时间超了0.2s

by michael_song @ 2020-02-15 18:48:28

@190040257a

这是我的代码

你重点看一下50多行

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int M=1010;
int n,m;
int head[M],indeg[M],result;
bool ki[M];
int a[M][M],ans[M],as[M];
queue <int> Q;
int maxn(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}
void tps()
{
    for(int i=1;i<=n;i++)
        if(!indeg[i])
        {
            Q.push(i);
            ans[i]=1;
        }
    while(!Q.empty())
    {
        int s=Q.front();
        Q.pop();
        for(int i=1;i<=n;i++)
        {
            if(a[s][i])
            {
                indeg[i]--;
                ans[i]=maxn(ans[s]+1,ans[i]);
                if(!indeg[i])
                    Q.push(i);
            }
        }
    }
}
int main()
{
    int i,j,k,si;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        memset(ki,false,sizeof(ki));
        memset(as,0,sizeof(as));
        scanf("%d",&si);
        for(j=1;j<=si;j++)
        {
            scanf("%d",&as[j]);
            ki[as[j]]=true;
        }
        for(j=as[1]+1;j<=as[si];j++)
            if(!ki[j])
                for(k=1;k<=si;k++) 
                    if(!a[j][as[k]]) 
                    {
                        a[j][as[k]]=1;
                        indeg[as[k]]++;
                    }
    }
    tps();
    for(i=1;i<=n;i++)
        result=maxn(result,ans[i]);
    printf("%d",result);
    return 0;
}

by 190040257a @ 2020-02-16 15:56:30

@michael_song 感觉我的代码跟你的思路差不多呀

by jijidawang @ 2020-02-21 16:17:38

@自动WA机私信我 领带