拓扑 WA on #6,#9,#10 求助

P1983 [NOIP2013 普及组] 车站分级

zhangjiting @ 2023-09-30 12:58:19

#include<bits/stdc++.h>
using namespace std;
int vis[1005],G[1005][1005],topo[1005],t,n,m,a[1005],c[1005],ans=1;
bool dfs(int u){
    vis[u]=-1;
    for(int v=1;v<=n;v++){
        if(G[u][v]){
            if(vis[v]<0) return false;
            if(!vis[v])if(!dfs(v)) return false;
        } 
    }
    vis[u]=1;
    topo[t--]=u;
    return true;
}
bool toposort(){
    t=n;
    memset(vis,0,sizeof(vis));
    for(int u=1;u<=n;u++){
        if(!vis[u]){
            if(!dfs(u)) return false;
        }
    }
    return true;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        memset(c,0,sizeof(c));
        int x;
        cin>>x;
        for(int j=1;j<=x;j++){
            cin>>a[j];c[a[j]]=1;
        }
        for(int j=1;j<=x;j++){
            for(int k=a[1];k<=a[x];k++){
                if(!c[k])G[a[j]][k]=1;
            }
        }
    }
    toposort();
    for(int i=1;i<=n;i++){
        if(G[topo[i]][topo[i+1]]){
            ans++;
        }
    }
    cout<<ans;
    return 0;
} 

|