Solution

首先考虑原图上有 \(n\) 条路径，每条路径只覆盖一个点。现在我们需要将尽可能多的路径合并在一起，得到最小覆盖路径。

那么考虑如何建模：
将每个点拆成 \(X_i\) 与 \(Y_i\) 两个点，分别表示该点的出点与入点。对于原图的边 \(<i,j>\) ，即连接 \(<X_i,Y_j>\)。
如此操作后得到一张二分图。左部点为出点，右部点为入点。
发现对于边 \(<X_i,Y_j>\) 的含义，其实就是将 \(i\) 所在路径与 \(j\) 所在路径合并在一起。
而我们需要将尽可能多的路径合并，即尽可能多的连边；同时每个点只能和其它点合并一次，即只能连一条边。
如此，问题就转化为二分图最大匹配。

所以，只需用网络流求出这张二分图的最大匹配数即可。
从源点 \(S\) 往所有左部点 \(X_i\) 连一条容量为 \(1\) 的边；从右部点 \(Y_i\) 往汇点 \(T\) 连一条容量为 \(1\) 的边；对于 \(<X_i,Y_j>\) ，使其容量为 \(1\)。
跑一边最大流得到的最大流量 \(res\) 即为最大匹配数。因为合并一次路径后路径总数会减一，故最后答案为 \(n - res\)。

最后，对于构造方案，遍历所有 \(<X_i,Y_j>\)，若其容量为 \(0\)，说明 \(X_i\) 与 \(Y_j\) 匹配，即最终方案中 \(i\)，\(j\) 之间相连。如此便可以得到方案。

Code

#include<bits/stdc++.h>
#define M 12605
#define N 305
using namespace std;
typedef long long ll;
typedef double db;
char IO;
int rd(){
	int num=0;bool f=0;
	while(IO=getchar(),IO<48||IO>57)if(IO=='-')f=1;
	do num=(num<<1)+(num<<3)+(IO^48);
	while(IO=getchar(),IO>=48&&IO<=57);
	return f?-num:num;
}
int to[M],nxt[M],val[M],hd[N],cnte=1;
void Adde(int u,int v,int w){
	to[++cnte]=v;val[cnte]=w;
	nxt[cnte]=hd[u];hd[u]=cnte;
}
void Add(int u,int v,int w){
	Adde(u,v,w);Adde(v,u,0);
}
int n,m,S,T;
int dep[N],cur[N];
queue<int> Q;
int BFS(){
	memset(dep,0,sizeof(dep));
	memcpy(cur,hd,sizeof(cur));
	dep[S]=1;Q.push(S);
	int u,v;
	while(!Q.empty()){
		u=Q.front();Q.pop();
		for(int i=hd[u];i;i=nxt[i]){
			if(!dep[v=to[i]]&&val[i])
				dep[v]=dep[u]+1,Q.push(v);
		}
	}
	return dep[T];
}
int DFS(int u,int flow){
	if(u==T)return flow;
	int f,res=0;int v;
	for(int i=cur[u];i&&flow;i=nxt[i]){
		cur[u]=i;v=to[i];
		if(dep[v]!=dep[u]+1)continue;
		if(val[i]&&(f=DFS(v,min(flow,val[i])))>0){
			val[i]-=f;
			val[i^1]+=f;
			res+=f;flow-=f;
		}
	}
	if(!res)dep[u]=0;
	return res;
}
int Lst[N],Nxt[N];
void Find(int u){
	if(!u)return ;
	printf("%d ",u);
	Find(Nxt[u]);
}
int main(){
	n=rd(),m=rd(),S=0,T=2*n+1;
	for(int i=1;i<=n;++i)
		Add(S,i+n,1),Add(i,T,1);
	int tmp=cnte;
	for(int i=1,u,v,w;i<=m;++i){
		u=rd(),v=rd();
		Add(u+n,v,1);
	}
	int res=0;
	while(BFS())
		res+=DFS(S,1e9);
	for(int i=tmp+1,u,v;i<=cnte;i+=2){
		v=to[i],u=to[i^1]-n;
		if(!val[i])Lst[v]=u,Nxt[u]=v;
	}
	for(int i=1;i<=n;++i){
		if(!Lst[i]){
			Find(i);
			puts("");
		}
	}
	cout<<n-res;
	return 0;
}