二分图染色法.md

二分图染色法

定义：一个无向图G是二部图当且仅当G中无奇数长度的回路

二分图相关：二分图的最大匹配、完美匹配和匈牙利算法

我们利用染色法来判断一个图是不是二分图，先找一个点为起点，然后把与它相连的点的颜色都变成与它相反的颜色,然后把这些点加入到队列中，如果这些点的颜色与父节点的不一样，就忽略，如果一样就证明了这个图不是二分图

NYOJ1015 二部图(染色法判断二分图)

const int N=200+20;
vector<int> G[N];
int color[N];
int bfs()
{
    queue<int>q;
    q.push(0);
    color[0]=1;
    while(!q.empty())
    {
        int v1=q.front();
        q.pop();
        for(int i=0; i<G[v1].size(); i++)
        {
            int v2=G[v1][i];
            if(color[v2]==-1)
            {
                color[v2]=-color[v1];
                q.push(v2);
            }
            else if(color[v1]==color[v2])
                return 0;
        }
    }
    return 1;
}
int main()
{
    int n,m,a,b;
    while(~scanf("%d",&n))
    {
        for(int i=0; i<N; i++)G[i].clear();
        mem(color,-1);
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d%d",&a,&b);
            G[a].push_back(b);
            G[b].push_back(a);
        }
        if(bfs())
            puts("BICOLORABLE.");
        else
            puts("NOT BICOLORABLE.");
    }
    return 0;
}

dfs版:hdu5917:给出一些点的颜色，问能不能分成两个集合

const int N = 1e5 + 10;
int n, m, x, y;
vector<int> e[N];
int color[N];
int dfs(int u)
{
    for (auto v : e[u])
    {
        if (color[v] == -1)
        {
            color[v] = -color[u];
            if (!dfs(v))
                return 0;
        }
        else if (color[u] == color[v])
            return 0;
    }
    return 1;
}
int main()
{
    // freopen("in.txt", "r", stdin);
    int u, v, val;
    while (~scanf("%d%d%d%d", &n, &m, &x, &y))
    {
        mem(color, -1);
        for (int i = 1; i <= n; i++)
            e[i].clear();
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d", &u, &v);
            e[u].push_back(v);
        }
        for (int i = 1; i <= x; i++)
        {
            scanf("%d", &val);
            color[val] = 1;
        }
        for (int i = 1; i <= y; i++)
        {
            scanf("%d", &val);
            color[val] = -1;
        }
        if (x == 0 && y == 0)
            puts("NO");
        else
        {
            int flag = 1;
            for (int i = 1; i <= n; i++)
                if (!dfs(i))
                    flag = 0;
            if (flag)
                puts("YES");
            else
                puts("NO");
        }
    }
    return 0;
}