#include<bits/stdc++.h>
using namespace std;

const int MAXN = 100; //假如最大100个结点的图
int graph[MAXN][MAXN];
int color[MAXN]; //用于确定分组,颜色为1和2

int dfs(int index,int n,int c) //仅仅用来染色出发点所在的连通分量
{
    //直接用对边不同色考虑
    color[index]=c;
    for(int i=0;i<n;i++) if(graph[index][i] && (color[i]==c || (color[i]==0 && !dfs(i,n,3-c))) ) return 0;
    return 1;
}

int main()
{
    int n,m;
    cin >> n >> m;
    for(int i=0;i<m;i++)
    {
        int s,t;
        cin >> s >> t;
        graph[s][t]=1,graph[t][s]=1;
    }
    for(int i=0;i<n;i++)
    {
        if(!color[i])
            if(!dfs(i,n,1)) 
            {
                cout << "错误，不是二分图" << endl;
                return 0;
            }
    }
    vector<int> color1,color2;
    for(int i=0;i<n;i++)
    {
        if(color[i]==1) color1.push_back(i);
        if(color[i]==2) color2.push_back(i);
    }
    cout << "染色结果:" << endl;
    for(int i=0;i<color1.size();i++) cout << color1[i] << ' ';
    cout << endl;
    for(int i=0;i<color2.size();i++) cout << color2[i] << ' ';

    return 0;
}

const int MAXN : 根据题目调整
int n : 两边的顶点总数
int graph[MAXN][MAXN] : 基于二维数组的邻接矩阵
int match[MAXN] : match[i]表示与i匹配的点(因为最大匹配饱和点中每一个点都只可能与唯一点匹配)，如果为-1表示未匹配
int used[MAXN] : dfs访问标记（这个级别低于匹配标记match）

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 20;// 根据题目调整
int n;// 两边的顶点总数
int graph[MAXN][MAXN];// 基于二维数组的邻接矩阵
int match[MAXN];// match[i]表示与i匹配的点(因为最大匹配饱和点中每一个点都只可能与唯一点匹配)，如果为-1表示未匹配
bool used[MAXN];// dfs访问标记（这个级别低于匹配标记match）

bool dfs(int x) //从x出发寻找增广路径
{
    for(int i=0;i<n;i++)
    {
        if(graph[x][i] && used[i]==false) //这里避免了递归i的对象时再次返回i的情况
        {
            used[i] = true; //打上dfs访问标记,防止循环卡死
            if(match[i]==-1 || dfs(match[i])==true) //i点就是未匹配点直接满足x-i加匹配 || i点是匹配过的点,从i点对象开始找到未匹配点  这两种都说明找到了增广路径
            {
                match[i] = x;
                match[x] = i;
                return true;
            }
        }
    }
    return false; //没true即false
}

//匈牙利算法求最大匹配数
int hungarian()
{
    fill(match,match+n,-1);
    int res=0;
    for(int i=0;i<n;i++)
    {
        if(match[i]==-1)
        {
            fill(used,used+n,false); //清除dfs标记
            if(dfs(i)) res++;
        }
    }
    return res;
}

int main()
{
    //举个例子
    n = 8;
    int tmp[8][8] = {
        {0,0,0,0,1,0,1,0},
        {0,0,0,0,1,0,0,0},
        {0,0,0,0,1,1,0,0},
        {0,0,0,0,0,0,1,1},
        {1,1,1,0,0,0,0,0},
        {0,0,1,0,0,0,0,0},
        {1,0,0,1,0,0,0,0},
        {0,0,0,1,0,0,0,0}
    };
    memcpy(graph, tmp, sizeof(tmp));
    cout << "最大匹配边数量:" << hungarian() << endl;
    return 0;
}