c++

#include <iostream>
bool DFS(int);
int bipartite_matching();

int nx, ny;             // X的點數目、Y的點數目
int mx[100], my[100];   // X各點的配對對象、Y各點的配對對象
bool vy[100];           // 記錄Graph Traversal拜訪過的點
bool adj[100][100];     // 精簡過的adjacency matrix


int main(int argc, const char * argv[]) {
    // insert code here...
    std::cout << "Hello, World!\n";

    nx=4;
    ny=5;

    int input;

    for(int i=0 ; i<nx;i++){
        for(int j=0;j<ny;j++){
            scanf("%d",&input);
            if(input){
                adj[i][j]=true;
            }else{
                adj[i][j]=false;
            }
        }
    }
    printf("bipartitie_matching:%d\n",bipartite_matching());


    return 0;
}



// 以DFS建立一棵交錯樹
bool DFS(int x)
{
    for (int y=0; y<ny; ++y)
        if (adj[x][y] && !vy[y])
        {
            vy[y] = true;

            // 找到擴充路徑
            //這個if有點厲害，一邊調整mx與my，一邊往下找尋augmenting path
            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;
}