算法——图论：判断二分图（染色问题）

题目：. - 力扣（LeetCode）

方法一：并查集

class Solution {
public:vector<int>father;int find(int x){if (father[x] != x)father[x] = find(father[x]);return father[x];}void add(int x1, int x2){int fa1 = find(x1), fa2 = find(x2);if (fa1 != fa2)father[fa1] = fa2;}bool isBipartite(vector<vector<int>>& graph) {father.resize(graph.size());for (int i = 0; i < graph.size(); i++){father[i] = i;}for (int i = 0; i < graph.size(); i++){//if (graph[i].size() == 1 || graph[i].size() == 0)continue;for (int j = 0; j < graph[i].size() ; j++){if(find(i)==find(graph[i][j]))return false;add(graph[i][j], graph[i][0]);}}// int cnt = 0;// for (int i = 0; i < graph.size(); i++)// {//     if (find(i) == i )cnt++;// }// return cnt==2;return true;}
};

注释的代码为一开始使用的方法，在处理完每个节点之后，从头到尾遍历每一个节点，找出所有祖先的个数。但是本题有可能出现不连通，即单个点。如果这样判断单个点也会算作其中，但是单个点可以属于任何一个集合，所以超过二也是正确的。

后来又尝试改进代码，仍然求出所有的祖先节点数，算上不连通点，最后判断总数是不是偶数。但是还是有问题，比如说有两群点以及一个单个的点，总共三个祖先节点，但是该单个点可以算作其中任何一群，所以是二分图，但是该程序会判断不是二分图。

后来干脆不管不连通点，先使用一个数组遍历标记每个点是不是不连通的，然后在最后求祖先节点的个数时，如果是不连通点则直接跳过。发现还是有问题。具体问题好像忘了？

最后又尝试使用set来判断，仍然不行。最后的最后将整个代码完全使用set，使用两个set，set1和set2，但是代码逻辑上有点问题导致有几个用例无法通过，虽然绝大多数都能通过。

总结出：大道至简。复杂的判断复杂的逻辑绕到最后可能还是错的。真正的解法应该很简单很美妙。如上述代码，判断结束条件为如果当前节点和其邻接点已经是同一个集合的了，则直接返回错误。否则如果到最后都没有发现错误则返回正确。

方法二：深搜

我们任选一个节点开始，将其染成红色，并从该节点开始对整个无向图进行遍历；

在遍历的过程中，如果我们通过节点 u 遍历到了节点 v（即 u 和 v 在图中有一条边直接相连），那么会有两种情况：

如果 v 未被染色，那么我们将其染成与 u 不同的颜色，并对 v 直接相连的节点进行遍历；

如果 v 被染色，并且颜色与 u 相同，那么说明给定的无向图不是二分图。我们可以直接退出遍历并返回 false 作为答案。

当遍历结束时，说明给定的无向图是二分图，返回 true 作为答案。

class Solution {
public:vector<int>color;bool vaild=true;void dfs(vector<vector<int>>& graph,int x,int c){color[x]=c;for(int i=0;i<graph[x].size();i++){if(color[graph[x][i]]==c){vaild=false;return;}else if(color[graph[x][i]]==0)dfs(graph,graph[x][i],c==1?2:1);}}bool isBipartite(vector<vector<int>>& graph) {color.resize(graph.size(),0);for(int i=0;i<graph.size();i++){if(color[i]==0)dfs(graph,i,1);}return vaild;}
};

方法三：广搜

思路与深搜类似

class Solution {
private:static constexpr int UNCOLORED = 0;static constexpr int RED = 1;static constexpr int GREEN = 2;vector<int> color;public:bool isBipartite(vector<vector<int>>& graph) {int n = graph.size();vector<int> color(n, UNCOLORED);for (int i = 0; i < n; ++i) {if (color[i] == UNCOLORED) {queue<int> q;q.push(i);color[i] = RED;while (!q.empty()) {int node = q.front();int cNei = (color[node] == RED ? GREEN : RED);q.pop();for (int neighbor: graph[node]) {if (color[neighbor] == UNCOLORED) {q.push(neighbor);color[neighbor] = cNei;}else if (color[neighbor] != cNei) {return false;}}}}}return true;}
};