#6002. 「网络流 24 题」最小路径覆盖

#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#include<set>#include<queue>#include<stack>#include<map>#include<vector>using namespace std;typedef long long ll;typedef pair<int,int> P;const int maxn=300,maxm=1e5+1000,inf=0x3f3f3f3f,mod=1e9+7;const ll INF=1e18+7;int n,m;vector<int>G[maxn];bool used[maxn];int cx[maxn],cy[maxn];bool vis[maxn];void pprintf(int u){    vis[u]=true;    if(cx[u]<0)    {        printf("\n");        return ;    }    printf(" %d",cx[u]);    pprintf(cx[u]);}bool dfs(int u){    for(int i=0; i<G[u].size(); i++)    {        int v=G[u][i];        if(used[v]) continue;        used[v]=true;        if(cy[v]<0||dfs(cy[v]))        {            cy[v]=u,cx[u]=v;            return true;        }    }    return false;}int solve(){    int res=0;    memset(cy,-1,sizeof(cy));    memset(cx,-1,sizeof(cx));    for(int i=1; i<=n; i++)    {        memset(used,false,sizeof(used));        res+=dfs(i);    }    memset(vis,false,sizeof(vis));    for(int i=1; i<=n; i++)    {        if(!vis[i])        {            printf("%d",i);            pprintf(i);        }    }    printf("%d\n",n-res);}int main(){    scanf("%d%d",&n,&m);    int u,v;    for(int i=1; i<=m; i++)    {        scanf("%d%d",&u,&v);        G[u].push_back(v);    }    solve();    return 0;}