交叉染色法

鉴于网上讲交叉染色的资料比较少，于是我把我自己的心得与方法贴出来，方便与大家共同进步。

二分图：

百度百科传送门

wiki百科传送门

判断一个图是否为二分图可以用交叉染色的方法来判断，可以用BFS，也可以用DFS，这里我用使用DFS来实现。

思路：

任意取一个点进行染色，如果发现要涂某一块时这个块已经被涂了色，并且与我们要使用的颜色不同的话，就说明这个图不能被染成BICOLORABLE的。

（1）如果没有染色，将它染色，并将它周围的点变成相反色。

（2）如果已经染色，判断是否与现在染色的点的颜色相同，相同，则退出，否则继续。

附上例题：UVA 10004 Bicoloring

CODE：
/

Problem Verdict Language Run Time Submission Date

10004 Bicoloring Accepted C++ 0.008 2012-11-01 13:14:52

/

#include

#include

#include

#include

usingnamespacestd;



constintMAXN =1001;



structEdge

{

intv, next;

}edge[MAXN];



intfirst[MAXN];

intvis[MAXN];//标记是否访问

boolcolor[MAXN];//二染色标记



intn, m;

intcnt;



voidread_graph(intu,intv)

{

edge[cnt].v = v;

edge[cnt].next = first[u], first[u] = cnt++;

}



intfind(intu)//交叉染色

{

for(inte = first[u] ; e != -1; e = edge[e].next)

{

intv = edge[e].v;

if(!vis[v])

{

vis[v] =1;

color[v] = !color[u];//将周围的点染成相反色

find(v);

}

elseif(color[v] == color[u])returnfalse;//若已经访问并且与当前需要染的颜色不相同，return false.

}

returntrue;

}





voidinit()

{

cnt =0;

memset(first, -1,sizeof(first));

memset(vis,0,sizeof(vis));

}





intmain()

{

while(~scanf("%d", &n) && n)

{

init();

scanf("%d", &m);

while(m--)

{

intu, v;

scanf("%d%d", &u, &v);

read_graph(u, v);

read_graph(v, u);

}

color[0] =1;

vis[0] =1;

if(find(0)) printf("BICOLORABLE.\n");

elseprintf("NOT BICOLORABLE.\n");

}

return0;

}

原文链接: https://www.cnblogs.com/g0feng/archive/2012/11/01/2750321.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍