type
status
password
date
slug
summary
category
URL
tags
icon
785.二分图的检测（一般指无向图）
二分图定义
二分图(中文翻译问题,有时也称作二部图)，是图论中的一种特殊模型。 如果图可以分为两部分: 绿色和蓝色，并且每一条连线都连接着一个绿色顶点和一个蓝色定点，则称这个图为一个二分图。右图就是一个二分图：
二分图检测
首先，选择一个节点，置为蓝色(绿色也可)。再将与之连线的节点置为对立的颜色——绿色，按深度优先(广度优先也可)的逻辑，将节点依次置为对立色，如果最终结果为：每条边都连接这一个蓝色和一个绿色节点,则二分图检测成功。
邻接表
环的检测
环的定义
在图论中，环（英语：cycle）是一条只有第一个和最后一个顶点重复的非空路径。
环的检测
度的判断（有向图、无向图都可以）
使用拓扑排序可以判断一个图中是否存在环，具体步骤如下：
- 求出图中所有结点的度。
- 将节点入栈，注意有向图与无向图的入栈条件不同
- 当栈不空时，弹出栈首元素，把与栈首元素相邻节点的度减一。如果相邻节点的度变为1（或者有向图的入度变为0），则将相邻结点入队。
- 循环结束时判断已经访问的结点数是否等于 n。等于 n 说明全部结点都被访问过，无环；反之，则有环。
并查集
只需要将边进行合并，并在合并之前判断是否已经联通即可，如果合并之前已经联通说明存在环。