方法一:并查集
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;
}
};