一、二分图
如果一个图的所有顶点可以被分为X和Y两个集合，所有边的顶点恰好一个属于X，另一个属于Y，且集合内的点互不相连，这样的图成为二分图。
算法思路：
1.先从一个未匹配的点 u 开始，任选一条从 u 出发的边 u->v，若v未配对，return；
若v已经配对，尝试update原来的配对关系；
2.若u v配对失败，重新选择 u 出发的边，继续匹配，直到配对成功，或者尝试完所有u出发的边；
3.继续其他点的匹配尝试；
int n,m,sum=0;
int e[9][9],book[9];
int match[100];
int dfs(int u){
int i;
for(i=n/2;i<=n;i++){ // 只需遍历Y集合
if(book[i]==0 && e[u][i] ==1){ //对任一点 u ，先从它的相邻边中找匹配顶点
book[i]=1;
if(match[i]==0 || dfs(match[i])){ // C.如果 i 未配对，或者找到了新的配对，才能执行以下更新
match[i]=u;
match[u]=i;
printf("%d->%d\t",u,i);
return 1;
}
}
}
return 0;
}
int main(){
int i,j,x,y;
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d %d",&x,&y);
e[x][y] =1;
e[y][x] =1;
}
for(i=1;i<=n;i++) match[i]=0;
for(i=1;i<=n/2;i++){ // A.只需遍历X集合
for(j=n/2;j<=n;j++) book[j]=0; // B.
if( dfs(i) ) sum++;
}
printf("\n%d ",sum);
getchar();getchar(); return 0;
}
二、总结
1.想不到的点：
a. X，Y仅仅是两个逻辑存在的集合，点都是在同一个无向图里面，所以可以for遍历，标记A处；但是不应该遍历图的所有点，只需遍历X集合，否则会出现意想不到的问题，比如：
这是遍历X集合的结果，即 for(i=1;i<=n/2;i++){ // A.；
这是遍历图的所有节点产生的结果，即 for(i=1;i<=n;i++){ // A.；
b. 对每个点 u 进行配对之前，要先把之前的标记已搜索点(Y集合)清空，标记B处
c. 被匹配点 i ，只有它未配对，或者它的原来配对对象可以重新找到配对对象的情况下，才能与 u 进行配对，这会触发dfs递归匹配操作，如果递归中有一组匹配失败，整个匹配都失败！