將所有點(diǎn)分成兩個(gè)集合，使得所有邊只出現(xiàn)在集合之間，就是二分圖
二分圖：一定不含有奇數(shù)個(gè)點(diǎn)數(shù)的環(huán)；可能包含長(zhǎng)度為偶數(shù)的環(huán)， 不一定是連通圖
染色可以使用1和2區(qū)分不同顏色，用0表示未染色
遍歷所有點(diǎn)，每次將未染色的點(diǎn)進(jìn)行dfs, 默認(rèn)染成1或者2
由于某個(gè)點(diǎn)染色成功不代表整個(gè)圖就是二分圖,因此只有某個(gè)點(diǎn)染色失敗就能立刻break/return文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-715047.html
染色失敗相當(dāng)于存在相鄰的2個(gè)點(diǎn)染了相同的顏色，即點(diǎn)的個(gè)數(shù)的奇數(shù)個(gè)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-715047.html
染色法判定二分圖：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10; // 由于是無(wú)向圖, 頂點(diǎn)數(shù)最大是N，那么邊數(shù)M最大是頂點(diǎn)數(shù)的2倍
int e[M], ne[M], h[N], idx;//鄰接表
int st[N];//該點(diǎn)的顏色
void add(int a, int b)
{
//頭插法
//如圖 如1與2之間要有一條線，讓2的ne為1，再讓h[1]為2的索引。
//這樣h[1]就是1節(jié)點(diǎn)存的最后一個(gè)相連的點(diǎn)，如圖就是7節(jié)點(diǎn)。
//而在索引表內(nèi)部，通過(guò)頭插法的方式(即每次ne指向上一個(gè)點(diǎn)(h存的就是上一個(gè)點(diǎn)))，索引表為：7->4->2
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool dfs(int u, int color)
{
st[u] = color;
for(int i = h[u]; i != -1; i = ne[i])
{//遍歷鄰接表
int j = e[i];
if(!st[j]) //若還沒(méi)顏色，則遞歸下去染色
{
//遞歸下去
if(!dfs(j, 3 - color)) return false;//如果當(dāng)前是3-2=1，則下一次是3-1=2，以此類推，奇數(shù)和偶數(shù)的點(diǎn)顏色不一樣
}
//如果該點(diǎn)有顏色，則判斷該點(diǎn)的顏色是否跟鄰接表的頭點(diǎn)顏色相同，相同則說(shuō)明矛盾
else if(st[j] == color) return false;
}
return true;
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m --)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b,a); // 無(wú)向圖，a->b, b->a
}
bool flag = true;
for(int i = 1; i <= n; i ++)
{
if(!st[i])
{
if(!dfs(i, 1))//如果返回FALSE，則說(shuō)明有矛盾發(fā)生，flag賦為FALSE
{
flag = false;
break;
}
}
}
if(flag) printf("Yes\n");
else printf("No\n");
return 0;
}
到了這里，關(guān)于搜索與圖論：染色法判定二分圖的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
