样例过，0分，拓扑求深度最大值

__Occasion_ @ 2023-05-31 18:30:53

#include<cstdio>
#include<string.h>
#include<queue>
using namespace std;
//undergroud
const int N=1e3+10;
int n,m,cnt,ans;
queue<int> q;
int vis[N],du[N],a[N],edge_vis[N][N],head[N],dep[N];
struct Node{
    int nxt,to;
}edge[N*N];
void add(int x,int y){
    edge[++cnt]={head[x],y},head[x]=cnt;
    return ;
}
void tuo(){
    for(int i=1;i<=n;i++) if(!du[i]) q.push(i),dep[i]=1;
    while(!q.empty()){
        int t=q.front();
        q.pop();
        for(int i=head[t];i;i=edge[i].nxt){
            int to=edge[t].to;
            dep[to]=dep[t]+1;
            ans=max(ans,dep[to]);
            if(--du[to]==0) q.push(to);
        }
    }
//  for(int i=1;i<=n;i++) printf("%d ",dep[i]);
//  puts("");
    printf("%d",ans);
}
void solve(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x;scanf("%d",&x);
        memset(vis,0,sizeof vis);
        for(int j=1;j<=x;j++){
            scanf("%d",&a[j]);
            vis[a[j]]=1;
        }
        for(int j=a[1];j<=a[x];j++)
            if(!vis[j])
                for(int p=1;p<=x;p++){
                    int ap=a[p];
                    if(!edge_vis[j][ap])
                        du[ap]++,add(j,ap),edge_vis[j][ap]=1;
                }
    }
    tuo();
    return ;
}
int main(){
    solve();
    return 0;
}

by Terry2011 @ 2023-06-01 14:31:01

#include<bits/stdc++.h>
using namespace std;
int n,m,ru[1001],a[1001][1001],s,k,cnt=-1,st,e;
bool vis[1001];
queue<int>q;
void read(int &p)
{
    p = 0;
    int k = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            k = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        p = p * 10 + c - '0';
        c = getchar();
    }
    p *= k;
    return;
}
void write_(int x)
{
    if(x < 0)
    {
        putchar('-');
        x = -x;
    }
    if(x>9)
    {
        write_(x/10);
    }
    putchar(x%10+'0');
}
void writesp(int x)
{
    write_(x);
    putchar(' ');
}
void writeln(int x)
{
    write_(x);
    putchar('\n');
}
int main(){
    read(n),read(m);
    for(int i=0;i<m;i++){
        memset(vis,0,sizeof(vis));
        read(s);
        for(int j=0;j<s;j++){
            read(k);
            if(j==0)st=k;
            if(j==s-1)e=k;
            vis[k]=1;
        }
        for(int j=st;j<=e;j++){
            if(!vis[j]){
                for(int z=st;z<=e;z++){
                    if(vis[z]&&a[z][j]==0){
                        a[z][j]=1;
                        ru[j]++;
                    }
                }
            }
        }
    }
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        a[0][i]=1;
        ru[i]++;
    }
    q.push(0);
    vis[0]=1;
    while(!q.empty()){
        cnt++;
        while(!q.empty()){
            int x=q.front();
            for(int i=1;i<=n;i++){
                if(a[x][i]&&vis[i]==0){
                    ru[i]--;
                }
            }
            q.pop();
        }
        for(int i=1;i<=n;i++){
            if(ru[i]==0&&vis[i]==0){
                vis[i]=1;
                q.push(i);
            }
        }
    }
    writeln(cnt);
    return 0;
}

by __Occasion_ @ 2023-06-03 08:10:38

@Terry2011 所以我源代码哪里错了？6

by Terry2011 @ 2023-06-10 11:31:44

@_Occasion 说实话，题目确实有点复杂，像这样的题目设个bool类型的数组好弄一点