求最大匹配的一種顯而易見(jiàn)的算法是：先找出全部匹配，然后保留匹配數(shù)最多的。但是這個(gè)算法的時(shí)間復(fù)雜度為邊數(shù)的指數(shù)級(jí)函數(shù)。因此，需要尋求一種更加高效的算法。
　　增廣路的定義(也稱增廣軌或交錯(cuò)軌)：
　　若P是圖G中一條連通兩個(gè)未匹配頂點(diǎn)的路徑，并且屬M(fèi)的邊和不屬M(fèi)的邊(即已匹配和待匹配的邊)在P上交替出現(xiàn)，則稱P為相對(duì)于M的一條增廣路徑。
　　由增廣路的定義可以推出下述三個(gè)結(jié)論：
　　1－P的路徑長(zhǎng)度必定為奇數(shù)，第一條邊和最后一條邊都不屬于M。
　　2－P經(jīng)過(guò)取反操作可以得到一個(gè)更大的匹配M’。
　　3－M為G的最大匹配當(dāng)且僅當(dāng)不存在相對(duì)于M的增廣路徑。
　　用增廣路求最大匹配(稱作匈牙利算法，匈牙利數(shù)學(xué)家Edmonds于1965年提出)
　　算法輪廓：
　　(1)置M為空
　　(2)找出一條增廣路徑P，通過(guò)取反操作獲得更大的匹配M’代替M
　　(3)重復(fù)(2)操作直到找不出增廣路徑為止
　　時(shí)間復(fù)雜度 鄰接矩陣：最壞為O(n^3) 鄰接表：O(nm)
　　空間復(fù)雜度 O(n^2) O(m+n)
　　程序清單：
 
#include<iostream>
#include<string>
#include<stdio.h>
using namespace std;
bool g[201][201];
int n,m,ans;
bool b[201];
int link[201];
//FILE *fin=fopen("stall4.in","r");
//FILE *fout=fopen("stall4.out","w");
void init()
{
    int _x,_y;
    memset(g,0,sizeof(g));
    memset(link,0,sizeof(link));
    ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&_x);
        for(int j=0;j<_x;j++)
        {
            scanf("%d",&_y);
            g[i][_y]=true;
        }
    }
}
bool find(int a)
{
    for(int i=1;i<=m;i++)
    {
        if(g[a][i]==true &&!b[i])
        {
            b[i]=true;
            if(link[i]==0||find(link[i]))
            {
                link[i]=a;
                return true;
               }
         }
     }
     return false;
}
int main()
{
    init();
    for(int i=1;i<=n;i++)
    {
        memset(b,0,sizeof(b));
        if(find(i))ans++;
    }
    printf("%d\n",ans);
    return 0;
}