小哼今天和小伙伴们一起去游乐场玩，终于可以坐上梦寐以求的过山车了。过山车的每一排只有两个座位，
为了安全起见，是每个女生必须和一个男生做一排。
但是，每个人都希望与自己认识的人坐在一起。如何安排才可以让更多认识的男生和女生坐在一起呢？
输入第一行为两个整数n,m。n表示有n个人（其中前1～n/2号为女生，n/2+1~n号为男生）,m表示有m个关系。(1 < n,m < 10)
后面m行，每行两个数a,b，表示a和b互相认识。
输出最大匹配个数（最多有几对男生女生可以坐在一起）
6 5
1 4
1 5
2 5
2 6
3 4
3
对于样例的解释：
1号女生和5号男生
2号女生和6号男生
3号女生和4号男生
一共三组（全部）匹配成功，所以最大匹配数是3。
1 #include<iostream>
2 //#include<fstream>
3 using namespace std;
4 int n,m;
5 int sum;
6 int book[103];//标记数组
7 int e[103][103];//存储图
8 int match[103];//存储配对关系
9 int dfs(int cur){
10 for(int i=1;i<=n;i++){//遍历每个点
11 if(book[i]==0&&e[cur][i]==1){//如果i这个点没被标记过并且cur点到i点有路
12 book[i]=1;//那么标记i点
13 if(match[i]==0||dfs(match[i])){//如果i点没有配对的点
14 //如果有配对的点的话，用dfs搜索i所配对的点，
15 //这样，i所配对的点可能会找到新的点，
16 //那么这时i就没有配对的点了
17 match[i]=cur;//将i和cur进行配对
18 match[cur]=i;
19 return 1;
20 }
21 }
22 }
23 return 0;
24 }
25 int main(){
26 // fstream file("haha.txt");
27 // file>>n>>m;
28 cin>>n>>m;
29 int a,b;
30 for(int i=1;i<=m;i++){
31 // file>>a>>b;
32 cin>>a>>b;
33 e[a][b]=1;
34 e[b][a]=1;
35 }
36 for(int i=1;i<=n;i++){
37 for(int j=1;j<=n;j++)//每次都要清空这个标记数组
38 book[j]=0;
39 if(dfs(i))
40 sum++;
41 }
42 cout<<sum;
43 return 0;
44 }
原文：https://www.cnblogs.com/fate-/p/12255043.html