8/9 基础思维+二分图染色+最大完美匹配KM算法

二分图判定染色法

大佬链接：https://www.bilibili.com/video/BV1sZ4y1i7NZ?spm_id_from=333.999.0.0&vd_source=91973ada1213cf6ba2cbb43a2bebd2e8

定理:二分图不存在奇环，只存在偶数环

#include
#define int long long
#define endl '\n'

using namespace std;
const int N=5e5+5;
const int inf=0x3f3f3f3f;
int n,m,cnt,head[N],color[N];
struct node
{
    int to,nxt;
}e[N];
void add(int from,int to)
{
    e[++cnt].to=to;
    e[cnt].nxt=head[from];
    head[from]=cnt;
}
bool dfs(int u,int c) //判断是否是二分图
{
    color[u]=c;
    for(int i=head[u];i;i=e[i].to)
    {
        int v=e[i].to;
        if(!color[v])
            if(dfs(v,3-c)) return 1;
        else if(color[v]==c)
            return 1;
    }
    return 0;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i>u>>v;
        add(u,v),add(v,u);
    }
    int flag=1;
    for(int i=1;i