@[zhibuba](/user/319478) 直接连边的复杂度不对吧
by do_while_true @ 2020-08-21 17:35:35
这个题的一半题解都是错的吧
by do_while_true @ 2020-08-21 17:36:16
此题跑拓扑排序的正确连边方法是建立虚拟节点，或者线段树优化建图
by do_while_true @ 2020-08-21 17:38:11
@[do_while_true](/user/223298) 虚拟节点是怎么弄？
by zhibuba @ 2020-08-22 23:23:32
@[zhibuba](/user/319478) 可以参考我这份代码
虚拟节点单独开出来，标记哪些节点是虚拟节点，在拓扑排序的时候遇到虚拟节点不更新答案。
```cpp
#include<iostream>
#include<cstdio>
#include<queue>
#define mp std::make_pair
#define pp std::pair<int,int>
const int N=10100;
inline int read()
{
int r=0,w=0;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-') w=1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
r=(r<<3)+(r<<1)+(ch^48);
ch=getchar();
}
return w ? ~r+1 : r;
}
int n,m,num;
int f[N<<1],ans,in[N<<1];
int fl[N<<1];
int cnt,head[N<<1];
struct node {
int to,nxt;
}e[N*N<<1];
int s[N],vis[N];
std::queue<int>q;
void add(int x,int y)
{
e[++cnt].to=y;
e[cnt].nxt=head[x];
head[x]=cnt;
in[y]++;
}
int main()
{
n=read();m=read();
num=n;
for(int i=1;i<=m;i++) {
int k=read();
int bnt=0;
for(int j=1;j<=k;j++)
s[j]=read();
for(int j=s[1];j<=s[k];j++)
vis[j]=0;
for(int j=1;j<=k;j++)
vis[s[j]]=1,bnt++;
if(bnt==s[k]-s[1]+1) continue;
++num;
fl[num]=1;
for(int j=s[1];j<=s[k];j++) {
if(!vis[j])
add(j,num);
else
add(num,j);
}
}
for(int i=1;i<=num;i++)
if(!in[i])
q.push(i),f[i]=1;
while(!q.empty()) {
int now=q.front();
q.pop();
ans=std::max(ans,f[now]);
for(int i=head[now];i;i=e[i].nxt) {
in[e[i].to]--;
f[e[i].to]=std::max(f[e[i].to],f[now]+(fl[e[i].to] ? 0 : 1 ));
if(!in[e[i].to])
q.push(e[i].to);
}
}
printf("%d",ans);
return 0;
}
```
by do_while_true @ 2020-08-22 23:44:03
如果对代码哪里有疑问可以问我
by do_while_true @ 2020-08-22 23:45:04
@[do_while_true](/user/223298) 懂了，多谢
by zhibuba @ 2020-08-22 23:58:14
@[do_while_true](/user/223298)
非常感谢~
对蒟蒻(我)特别有帮助！~
by theHermit @ 2020-08-29 09:34:09