poj1422 Air Raid 二分匹配之最小路径覆盖

典型的最小路径覆盖题，城市之间单向相连，无环！问最少用多少个伞兵能遍历这张图。
根据定理：最小路径覆盖=顶点数-最大匹配数

Source Code
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
    int nx, ny;             // X的點數目、Y的點數目
int mx[121], my[121];   // X各點的配對對象、Y各點的配對對象
bool vy[121];           // 紀錄Graph Traversal拜訪過的點
bool adj[121][121];     // 精簡過的adjacency matrix
// 以DFS建立一棵交錯樹
bool DFS(int x)
{
    for (int y=0; y<ny; ++y)
        if (adj[x][y] && !vy[y])
        {
            vy[y] = true;
            // 找到擴充路徑
                if (my[y] == -1 || DFS(my[y]))
            {
                mx[x] = y; my[y] = x;
                return true;
               }
        }
    return false;
}
int bipartite_matching()
{
    // 全部的點初始化為未匹配點。
    memset(mx, -1, sizeof(mx));
        memset(my, -1, sizeof(my));
    // 依序把X中的每一個點作為擴充路徑的端點，
    // 並嘗試尋找擴充路徑。
    int c = 0;
    for (int x=0; x<nx; ++x)
//     if (mx[x] == -1)    // x為未匹配點，這行可精簡。
        {
            // 開始Graph Traversal
            memset(vy, false, sizeof(vy));
            if (DFS(x)) c++;
        }
    return c;
}
main()
{
          int i,a,b,t,n,m;
          scanf("%d",&t);
          while(t--)
          {
            scanf("%d%d",&n,&m);
            memset(adj,0,sizeof(adj));
            for(i=0;i<m;i++)
            {
              scanf("%d%d",&a,&b);
              adj[a-1][b-1]=1;
            }
            nx=ny=n;
            printf("%d\n",n-bipartite_matching());
          }
          system("pause");
}