关于queue的时间复杂度问题

RT，我的第一份代码把级数和节点（停靠站的编号）一起作为结构体存入queue，第二份代码只在queue里存了节点，另开了一个数组解决了级数的问题。可以看到，两份代码只在拓扑排序部分有些许不同（如上描述），但第一份代码得了80pts，第二份代码却轻松AC。所以想请教一下大佬，这真的是queue的锅吗（我记得queue的插入和删除操作都是 O(log\;n) 的吧）？

Code 1：

#include<bits/stdc++.h>
using namespace std;

int station[1005];
int vis[1005];
map<int,int> G[1005];
vector<int> g[1005];
int in_d[1005];

struct node{
    int num;//用num来记录级数
    int i;
};

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int sta;//station
        scanf("%d",&sta);
        memset(vis,0,sizeof(vis));
        memset(station,0,sizeof(station));
        for(int j=1;j<=sta;j++){
            scanf("%d",&station[j]);
            vis[station[j]]=1;
        }
        //建立有向无环图
        for(int j=station[1];j<=station[sta];j++){//从起点到终点
            if(vis[j]==0){//不是停靠点
                for(int k=1;k<=sta;k++){
                    int a=j;
                    int b=station[k];//从a向b连边
                    if(G[a][b]==0){//防重边
                        G[a][b]=1;
                        g[a].push_back(b);
                        in_d[b]++;
                    }
                }
            }
        }
    }
    queue<node> q;
    for(int i=1;i<=n;i++){
        if(in_d[i]==0){
            q.push({1,i});
        }
    }
    int ans=0;
    while(!q.empty()){
        node t=q.front();
        q.pop();
        ans=max(ans,t.num);
        for(auto it=g[t.i].begin();it!=g[t.i].end();it++){
            in_d[*it]--;
            if(in_d[*it]==0){
                q.push({t.num+1,*it});
            }
        }
    }
    printf("%d",ans);
    return 0;
}

80pts的提交记录

Code 2：

#include<bits/stdc++.h>
using namespace std;

int station[1005];
int vis[1005];
int G[1005][1005];
vector<int> g[1005];
int in_d[1005];
int level[1005];

struct node{
    int num;//用num来记录级数
    int i;
};

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int sta;//station
        scanf("%d",&sta);
        memset(vis,0,sizeof(vis));
        memset(station,0,sizeof(station));
        for(int j=1;j<=sta;j++){
            scanf("%d",&station[j]);
            vis[station[j]]=1;
        }
        //建立有向无环图
        for(int j=station[1];j<=station[sta];j++){//从起点到终点
            if(vis[j]==0){//不是停靠点
                for(int k=1;k<=sta;k++){
                    int a=j;
                    int b=station[k];//从a向b连边
                    if(G[a][b]==0){//防重边
                        G[a][b]=1;
                        g[a].push_back(b);
                        in_d[b]++;
                    }
                }
            }
        }
    }
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(in_d[i]==0){
            q.push(i);
            level[i]=1;
        }
    }
    int ans=0;
    while(!q.empty()){
        int t=q.front();
        q.pop();
        for(auto it=g[t].begin();it!=g[t].end();it++){
            in_d[*it]--;
            if(in_d[*it]==0){
                q.push(*it);
                level[*it]=max(level[*it],level[t]+1);//为了满足*it级数必须大于t，故取max
            }
        }
    }
    for(int i=1;i<=n;i++){
        ans=max(ans,level[i]);
    }
    printf("%d",ans);
    return 0;
}

100pts的提交记录