用图的「二染色」判断:将每个连通分量用 BFS/DFS 染成两种颜色(如 1 和 -1)。遍历边 (u,v),若两端颜色相同则不是二分图。
关键点:
给定一个表示无向图的图的节点和边的列表,请判断该图是否是一个二分图。
二分图定义:
一个图如果可以将其节点集合划分为两个独立的 子集,使得每条边的两个顶点分别属于不同的子 集,那么这个图就是二分图。
输入
4,[[1,2],[2,3][3,4],[4,1]]
输出
true
说明
本题属于以下题库,请选择所需题库进行购买
ScanQRCodePrompt