pencil @ 2020-09-11 21:08:12
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int q[N*N],h[N],ne[N*N],e[N*N],idx=0,ru[N],que[N*N],w[N],ji[N];
void add(int a,int b,int w1) {
e[idx]=a;
ne[idx]=h[a];
w[idx]=w1;
h[a]=idx++;
}
int main() {
int n,m,o,i,n2;
cin>>n>>m;
memset(h,-1,sizeof(h));
int a,big,sma,xu;
for(o=1; o<=m; o++) {
cin>>n2;
big=0;
sma=n;
for(i=1; i<=n2; i++) {
cin>>a;
big=max(big,a);
sma=min(sma,a);
ji[a]=1;
}
xu=n+o;
for(i=sma; i<=big; i++) {
if(!ji[i]) {
add(i,xu,0);
ru[xu]++;
} else {
add(xu,i,1);
ru[i]++;
}
}
}
for(i=1; i<=n+m; i++) cout<<i<<":"<<ru[i]<<" ";
cout<<endl;
int tail=-1,bigg=1,tt,head=0,op;
for(i=1; i<=n+m; i++) {
if(!ru[i]) {
tail++;
que[tail]=i;
}
}
memset(q,1,sizeof(q));
while(head<=tail) {
op=que[head++];
for(int j=h[op]; j!=-1; j=ne[j]) {
tt=e[j];
q[tt]=max(q[tt],q[op]+w[j]);
//cout<<"h[op]:"<<h[op]<<" ";cout<<"h[op]:"<<h[op]<<" ";
bigg=max(q[tt],bigg);
cout<<j<<":"<<bigg<<" ";
ru[tt]--;
if(!ru[tt]) {
que[++tail]=tt;
}
}
}
// for(i=1; i<=n+m; i++) {
// op=que[i];
// for(int j=h[op]; j!=-1; j=ne[j]) {
// tt=e[j];
//
//
// }
// }
cout<<bigg;
return 0;
}