这题有个转化，求最少的链覆盖→即求最少联通块。
设联通块个数$x$个,选的边数$y$,点数$n$个
那么有 $y=n-x$ 即 $x=n-y$
而n是不变的,目标就是在保证每个点入度、出度不大于1的前提下让选的边尽可能地多。
下面网络流建模。
利用二分图匹配建图，左右两点集都包含 n 个点，左点集代表 u 的出度，右点集代表 u 的入度。对于原图中的边 (u,v)，从 左边的u点 向 右边的v点 连一条容量为 1 的 边，左点集与超级源点、右点集与超级汇点都分别连一条容量 1 的边，然后从源点做最大流，容量设1保证了我们每个点只流向另外唯一一个点，不会重叠。最大流即为所选边在满足条件下的最多数量。答案就是$n-y$。
spj那个的话就只要找到每一块的起点，也就是入度为0，这个看代码。找到起点就往后查残量为0的边顺着跑到底就行啦。
注意，这个只能是对DAP有效。有环的话就不行了，连通块会多余边会被流过，可以画一下。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef pair<int,int> pii; 5 template<typename T>inline char MIN(T&A,T B){return A<B?A=B,1:0;} 6 template<typename T>inline char MAX(T&A,T B){return A>B?A=B,1:0;} 7 template<typename T>inline T _min(T A,T B){return A<B?A:B;} 8 template<typename T>inline T _max(T A,T B){return A>B?A:B;} 9 template<typename T>inline T read(T&x){ 10 x=0;char c;while(!isdigit(c=getchar()))if(isalpha(c))return x=(int)c; 11 while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();return x; 12 } 13 const int N=150+7,M=10000+7,INF=0x3f3f3f3f; 14 int w[M<<1],v[M<<1],Next[M<<1],Head[N<<1],cur[N<<1],dis[N<<1],tot=1,s,t,n,m; 15 inline void Addedge(int x,int y,int z){ 16 v[++tot]=y,Next[tot]=Head[x],Head[x]=tot,w[tot]=z; 17 v[++tot]=x,Next[tot]=Head[y],Head[y]=tot,w[tot]=0; 18 } 19 #define y v[j] 20 inline char bfs(){ 21 queue<int> q;q.push(s),memset(dis,0,sizeof dis),dis[s]=1; 22 for(register int i=1;i<=(n<<1)+2;++i)cur[i]=Head[i]; 23 while(!q.empty()){ 24 int x=q.front();q.pop(); 25 for(register int j=Head[x];j;j=Next[j])if(w[j]&&!dis[y]){ 26 dis[y]=dis[x]+1,q.push(y); 27 if(y==t)return 1; 28 } 29 } 30 return 0; 31 } 32 int dinic(int x,int flow){ 33 if(!flow||x==t)return flow; 34 int rest=flow,k; 35 for(register int j=cur[x];j&&rest;cur[x]=j,j=Next[j])if(w[j]&&dis[y]==dis[x]+1){ 36 if(!(k=dinic(y,_min(rest,w[j]))))dis[y]=0; 37 rest-=k,w[j]-=k,w[j^1]+=k; 38 } 39 return flow-rest; 40 } 41 #undef y 42 int x,y,ans; 43 inline void print(int x){ 44 printf("%d ",x); 45 for(register int j=Head[x];j;j=Next[j])if(v[j]<s&&!w[j])print(v[j]-n); 46 } 47 48 int main(){//freopen("tmp.in","r",stdin);freopen("tmp.out","w",stdout); 49 read(n),read(m);s=2*n+1,t=2*n+2; 50 for(register int i=1;i<=n;++i)Addedge(s,i,1); 51 for(register int i=n+1;i<=n*2;++i)Addedge(i,t,1); 52 for(register int i=1;i<=m;++i)read(x),read(y),Addedge(x,y+n,1); 53 while(bfs())ans+=dinic(s,INF); ans=n-ans; 54 for(register int i=n+1;i<s;++i){// s <==> n*2+1 55 int tmp=0; 56 for(register int j=Head[i];j;j=Next[j])if(v[j]<=n&&w[j]){tmp=1;break;} 57 if(!tmp)print(i-n),puts(""); 58 } 59 printf("%d ",ans); 60 return 0; 61 }