二分图判定

约 381 个字 38 行代码 预计阅读时间 2 分钟

二分图相关概念

图的点集可以被分为两部分，每一部分的内部都没有连边

完全二分图/满二分图(Complete bipartite graph/Biclique)： 二分图中任何两个不在同一部分的点之间都有连边

匹配(Matching)(又叫边独立集 (Independent edge set))： 对于图G，E的子集E'中任意两条不同的边都没有公共的端点， 且E'中任意一条边都不是自环，则E'是图G的一个匹配， 例子： 一夫一妻制，任一丈夫都只有一个妻子，任一妻子都只有一个丈夫

如果一个点是匹配中某条边的一个端点， 则称这个点是 被匹配的 (matched)/饱和的 (saturated)， 否则称这个点是 不被匹配的 (unmatched)。

极大匹配(Maximal matching)： 一个匹配，满足加入任何一条边后都不再是一个匹配

最大匹配(Maximum-cardinality matching)： 边数最多的匹配 最大的极大匹配就是最大匹配

最大权匹配 (Maximum-weight matching)： 边权之和最大的匹配

完美匹配 (Perfect matching)： 一个匹配，满足所有点都是被匹配的

增广路径(Augmenting path)： 一个匹配M，满足一条路径以非匹配点为起点和终点，每相邻两条边的其中一条在匹配中而另一条不在匹配中

二分图判定

按照和起点的距离的奇偶性分类，黑白染色，若相同奇偶性不同色，则不是二分图

int col[N];
vector<int> ed[N];
bool judgeBfs(int r)
{
    col[r]=1;
    queue<int> d;
    d.push(r);
    int u;
    while(!d.empty())
    {
        u=d.front();
        d.pop();
        for(int v:ed[u])
        {
            if(col[v]==0)
            {
                col[v]=-col[u];
                d.push(v);
            }
            else if(col[v]==col[u])
                return false;
        }
    }
    return true;
}
bool judge()
{
    memset(col,0,sizeof(col));
    for(int i=1;i<=n;++i)
    {
        if(!col[i])
        {
            if(!judgeBfs(i))
                return false;
        }
    }
    return true;
}