染色法判二分

//无向图G为二分图的充分必要条件是：G至少有两个顶点,且当存在回路时，其所有回路的长度均为偶数。回路就是环路，也就是判断是否存在奇数环。

int check[109];

int dfs(int u, int flag)
{
int i;
for(i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if(check[v] == 0)
{
check[v] = flag ^ 1;
dfs(v, flag ^ 1);
}
else if(chcek[v] == flag)
{
return -1;
}
}
}

//二分图最大匹配

void find(int u)
{
int i;
for(i = 1; i <= m; i++)
{
if(con[u][i] && vis[i] == 0)
{
vis[i] = 1;
if(log[i] == 0 || find(log[i]))
return true;
}
}
return false;
}

int main()
{
int i;
int num = 0;
for(i = 1; i <= n; i++)
{
memset(vis, 0, sizeof(vis));
if(find(i))
num++;
}
printf(“%d\n”, num);
return num;
}

染色法判二分

原文：https://www.cnblogs.com/daybreaking/p/12782852.html