_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数据是记录等级的 感谢各位大佬!