拓扑求助!

P1983 [NOIP2013 普及组] 车站分级

_weishiqi66_ @ 2023-02-05 14:01:49

#include<bits/stdc++.h>
#define ll long;
const int N=int(1e3)+1;
using namespace std;

int n,m,cnt,ans,tn;
int k,head[N],p[N],in[N],lv[N]; 
bool f[N];
struct uc{
    int to,next;
}a[N];
void add(int x,int y){
    ++cnt;
    a[cnt].to=y;
    a[cnt].next=x;
    head[x]=cnt;
}
void topsort(){
    queue<int> q;
    for(int i=1;i<=tn;i++){
        if(in[i]==0){
            q.push(i);
            lv[i]=1;
        }
    }
    while(!q.empty()){
        int tmp=q.front(); q.pop();
        for(int i=head[tmp];i;i=a[i].next){
            int v=a[i].to;
            lv[v]=lv[tmp]+1;
            ans=max(ans,lv[v]);
            in[v]--;
            if(in[v]==0) q.push(v);
        }
    }
    return;
}
int main(){
    std::ios::sync_with_stdio(0);
    cin>>n>>m;
    tn=n;
    for(int i=1;i<=m;i++){
        cin>>k;
        for(int j=1;j<=k;j++) cin>>p[j],f[p[j]]=1;
        for(int j=p[1];j<=p[k];j++){
            if(f[j]==1) add(j,tn);
            if(f[j]==0) add(tn,j);
        }
        tn++;
    }
    cout<<114514;
    topsort();
    cout<<ans;
    return 0;
}

by _weishiqi66_ @ 2023-02-05 14:04:50

有一个问题,就是我在本地测试时发现的。 就是 第51行的cout<<114514; 如果测数据就会发现输出不了,我本以为是我上面的for循环卡了。但是发现把 52行的 topsort 注释掉时就可以输出。

这是为什么呢?程序不是一行一行的运行的吗?为什么我拓扑写炸了会影响到上面呢?


by _weishiqi66_ @ 2023-02-05 14:05:57

in数组是记录边数量的 lv数据是记录等级的 感谢各位大佬!


|