交叉染色法判斷二分圖

預處理：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <queue>
using namespace std;

const int MAXN = 210;
const int MAXM = 210*210;

struct Edge
{
    int v, next;
}edge[MAXM];

int n, m;
int cnt;

int first[MAXN];
bool vis[MAXN], color[MAXN];

void init()
{
    cnt = 0;
    memset(first, -1, sizeof(first));
    memset(color, 0, sizeof(color));
    memset(vis, 0, sizeof(vis));
}
           

DFS實作：

bool Bicolor(int u)
{
	for(int e = first[u]; e != -1; e = edge[e].next)
	{
		int v = edge[e].v;
		if(!vis[v])
		{
			vis[v] = true;
			color[v] = !color[u];
			Bicolor(v);
		}
		else if(color[u] == color[v]) return false;
	}
	return true;
}

void solve(int src)
{
	vis[src] = 1; //很重要 
	if(Bicolor(src)) printf("Bicolor\n");
	else printf("Un Bicolor\n")
}

           

BFS實作：

queue<int> q;
bool Bicolor(int src)
{   
	while(!q.empty()) q.pop();
    q.push(src);
    while(!q.empty())  
    {  
        int u = q.front(); q.pop();
        for(int e = first[u]; e != -1; e = edge[e].next)
        {
			int v = edge[e].v;
            if(!vis1[v])
            {
				vis1[v] = 1;
                color[v] = !color[u];
                q.push(v);
            }
            else if(color[u] == color[v]) return false;
        }
    }
    return true;
}