rt
第五个点下下来本地过了,在IDE上也过了
但是luogup 评测RE
#include<bits/stdc++.h>
#define reg register
#define Mod(x) (((x)+mod)%mod)
#define IN freopen(".in.txt","r",stdin)
#define OUT freopen(".out.txt","w",stdout)
#define int long long
using namespace std;
const int N=1e4+10,INF=1e18;
int n,m,s,t,cnt=1,head[N];
int nxt[N],tag[N];
queue<int> q;
int dep[N],cur[N],gap[N],check[N];
struct EDGE{
int pre,from,to,val;
}edge[N<<1];
inline int read(){
int k=1,x=0;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') k=-1; ch=getchar();}
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=getchar();
return k*x;
}
inline void add(reg int u,reg int v,reg int w){edge[++cnt]=(EDGE){head[u],u,v,w},head[u]=cnt;}
inline bool bfs(){
memset(dep,0,sizeof(dep));
dep[s]=1,q.push(s);
for (reg int i=1;i<=n;i++) cur[i]=head[i];
while (!q.empty()){
reg int u=q.front(); q.pop();
for (reg int i=head[u];i;i=edge[i].pre){
int v=edge[i].to;
if (edge[i].val&&!dep[v]) dep[v]=dep[u]+1,q.push(v);
}
}
return dep[t];
}
inline int dfs(int u,int flow){
if (u==t) return flow;
int dout=0;
for (reg int i=cur[u];i&&flow;i=edge[i].pre){
reg int v=edge[i].to;
cur[u]=i;
if (edge[i].val&&dep[v]==dep[u]+1){
reg int res=dfs(v,min(flow,edge[i].val));
if (res){
nxt[u]=v;
if (u!=s) tag[v-n]=1;
edge[i].val-=res,edge[i^1].val+=res;
flow-=res,dout+=res;
}
if (!flow) break;
}
}
if (!dout) dep[u]=0;
return dout;
}
int sum;
signed main(){
n=read(),m=read(),s=n+n+1,t=n+n+2;
for (reg int i=1;i<=n;i++) add(s,i,1),add(i,s,0),add(i+n,t,1),add(t,i+n,0);
for (reg int i=1,u,v;i<=m;i++) u=read(),v=read()+n,add(u,v,1),add(v,u,0);
memset(check,1,sizeof(check));
reg int ans=0;
while (bfs()) memcpy(cur,head,sizeof(head)),ans+=dfs(s,1e18);
// cout<<1;
// memset(tag,1,sizeof(tag));
for (reg int i=1,u;i<=n;i++)
if (!tag[i]){
printf("%lld",i),u=i;
while (nxt[u]!=s&&nxt[u]!=t&&nxt[u]-n>0) printf(" %lld",u=nxt[u]-n);
puts("");
}
printf("%lld",n-ans);
return 0;
}
//.................................................................................................................
//.................................................................................................................
//.................................................................................................................
//.......RRRRRRRRRRRRRRRRRRRR...................PPPPPPPPPPPPPPPPPPPP...............................................
//.......RRRRRRRRRRRRRRRRRRRRRR.................PPPPPPPPPPPPPPPPPPPPPP.............................................
//.......RRRRRRRRRRRRRRRRRRRRRRR................PPPPPPPPPPPPPPPPPPPPPPPP...........................................
//.......RRRR.................RRRRR.............PPPP...............PPPPP...........................................
//.......RRRR.................RRRRR.............PPPP................PPPPP..........................................
//.......RRRR.................RRRRR.............PPPP................PPPPP..........................................
//.......RRRR...............RRRRR...............PPPP...............PPPPP...........................................
//.......RRRR............RRRRRR.................PPPP.............PPPPPP............................................
//.......RRRR............RRRRRR.................PPPP............PPPPPP.............................................
//.......RRRR........RRRRRR.....................PPPP........PPPPPP.................................................
//.......RRRRRRRRRRRRRRRRRR.....................PPPPPPPPPPPPPPPPPP.................................................
//.......RRRRRRRRRRRRRRRRRR.....................PPPPPPPPPPPPPPPP...................................................
//.......RRRR..........RRRR.....................PPPPP.................................+++................+++.......
//.......RRRR...........RRRR....................PPPPP.................................+++................+++.......
//.......RRRR.............RRRR..................PPPPP.................................+++................+++.......
//.......RRRR..............RRRR.................PPPPP...........................+++++++++++++++....+++++++++++++++.
//.......RRRR...............RRRR................PPPPP...........................+++++++++++++++....+++++++++++++++.
//.......RRRR................RRRR...............PPPPP.................................+++................+++.......
//.......RRRR.................RRRR..............PPPPP.................................+++................+++.......
//.......RRRR...................RRRR............PPPPP.................................+++................+++.......
//.................................................................................................................
//.................................................................................................................
//.................................................................................................................
//.................................................................................................................