最小路径覆盖
二分图定理：最小路径覆盖数=顶点数-最大匹配
简单证明：一开始每个点都独立的为一条路径，总共有n条不相交路径。我们每次在二分图里加一条边就相当于把两条路径合成了一条路径，因为路径之间不能有公共点，所以加的边之间也不能有公共点，这就是匹配的定义。所以有：最小路径覆盖数=顶点数-最大匹配。
有这个定理就简单了，求一遍最大匹配就好了。
1.把每个点拆成两个点：入点和出点。
2.建一个超级源点，向每个出点连一条流量为1的边
3.建一个超级汇点，每个入点向它连一条流量为1的边
4.根据给的边(i,j)，把i的出点连向j的入点
最后是输出路径，在网络流跑完后的残图中找为0的边，用并查集维护一下就好了。
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int inf=1e9;
int n,m,x,y,z,s,t,ans,d[10005];
struct node{
int next,to,w;
}a[500000];
int cnt=1,head[10005],cur[10005],f[10005],vis[10005];
queue <int> q;
void add(int x,int y,int dis)
{
a[++cnt].next=head[x];
a[cnt].to=y;
a[cnt].w=dis;
head[x]=cnt;
}
int find(int u)
{
if(f[u]==u) return u;
else return f[u]=find(f[u]);
}
bool bfs(int s,int t)
{
memset(d,0x7f,sizeof(d));
while(!q.empty()) q.pop();
for(int i=0;i<=2*n+1;i++) cur[i]=head[i];
d[s]=0;
q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=a[i].next)
{
int v=a[i].to;
if(d[v]>inf&&a[i].w)
{
d[v]=d[u]+1;
q.push(v);
}
}
}
if(d[t]<inf) return true;
else return false;
}
int dfs(int now,int t,int limit)
{
if(!limit||now==t) return limit;
int flow=0,f;
for(int i=cur[now];i;i=a[i].next)
{
cur[now]=i;
int v=a[i].to;
if(d[v]==d[now]+1&&(f=dfs(v,t,min(limit,a[i].w))))
{
flow+=f;
limit-=f;
a[i].w-=f;
a[i^1].w+=f;
if(!limit) break;
}
}
return flow;
}
void output(int x)
{
printf("%d ",x);
vis[x]=1;
for(int i=head[x];i;i=a[i].next)
if(a[i].w==0&&a[i].to>n)
output(a[i].to-n);
}
int main()
{
scanf("%d%d",&n,&m);
s=0;t=2*n+1;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y+n,1); //把x的出点和y的入点连边
add(y+n,x,0);
}
for(int i=1;i<=n;i++)
add(0,i,1),add(i,0,0),add(i+n,t,1),add(t,i+n,0);
//建一个超级源点，向每个出点连一条流量为1的边;建一个超级汇点，每个入点向它连一条流量为1的边
while(bfs(s,t)) ans+=dfs(s,t,inf);//跑一遍网络流
for(int i=1;i<=n;i++) f[i]=i;
for(int i=0;i<=cnt;i++) //并查集维护
if(a[i].next>=1&&a[i].next<=n&&a[i].to>n&&a[i].to<t&&a[i].w==0)
f[find(a[i].to-n)]=find(a[i].next);
for(int i=1;i<=n;i++)
if(find(i)==i&&(!vis[i]))
output(i),printf("\n");//输出路径
printf("%d",n-ans);
return 0;
}