1. 题目

传送门=￣ω￣=

2. 题解

DAG 的最小不相交路径覆盖问题

算法：把原图的每个点V拆成Vx和Vy两个点，如果有一条有向边A->B，那么就加边Ax−>By。这样就得到了一个二分图。那么最小路径覆盖=原图的结点数-新图的最大匹配数。

证明：一开始每个点都是独立的为一条路径，总共有 n 条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径，也就相当于路径数减少了 1。所以找到了几条匹配边，路径数就减少了多少。所以有最小路径覆盖=原图的结点数-新图的最大匹配数。

因为路径之间不能有公共点，所以加的边之间也不能有公共点，这就是匹配的定义。

（以上摘自 https://www.cnblogs.com/justPassBy/p/5369930.html）

因此偷懒跑个匈牙利就行了。

代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,match[405],ans;
vector<int> g[405];
bool book[405];
void con(int a,int b){match[a]=b,match[b]=a;}
bool dfs(int a)
{
    for(int i=0;i<g[a].size();i++)if(!book[g[a][i]])
    {
        book[g[a][i]]=1;
        if(!match[g[a][i]]){con(a,g[a][i]);return 1;}
        if(dfs(match[g[a][i]])){con(a,g[a][i]);return 1;}
    }
    return 0;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,a,b;i<=m;i++)scanf("%d%d",&a,&b),g[a].push_back(b+n);
    for(int i=1;i<=n;i++)if(!match[i])
        memset(book,0,sizeof(book)),ans+=dfs(i);
    memset(book,0,sizeof(book));
    for(int i=1;i<=n;i++)if(!book[i])
    {
        for(int j=i;j>0;j=match[j]-n)
            book[j]=1,printf("%d ",j);
        putchar('\n');
    }
    printf("%d\n",n-ans);
    return 0;
}