poj 2594Treasure Exploration(有向图路径可相交的最小路径覆盖)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define N 505
using namespace std;

int g[N][N];
int n, m;
int vis[N], linker[N];
bool dfs(int u){
   for(int i=1; i<=n; ++i)
      if(g[u][i] && !vis[i]){
          vis[i]=1;
          if(!linker[i] || dfs(linker[i])){
              linker[i]=u;
              return true;              
          }
      }
   return false;
}

int main(){
   while(scanf("%d%d", &n, &m) && (n||m)){
       memset(g, 0, sizeof(g));
       while(m--){
          int u, v;
          scanf("%d%d", &u, &v);
          g[u][v]=1;           
       }                    
       for(int k=1; k<=n; ++k)
          for(int i=1; i<=n; ++i)
             for(int j=1; j<=n; ++j)
               if(!g[i][j])
                  g[i][j]=g[i][k]&&g[k][j];
       memset(linker, 0, sizeof(linker));
       int ans=0;
       for(int i=1; i<=n; ++i){
           memset(vis, 0, sizeof(vis));
           if(dfs(i))  ++ans;        
       }
       printf("%d\n", n-ans);
   }
   return 0;    
}