网站制作流程图,网站怎么增加页面收录,自己开发一个app要多少钱,一点优化. - 力扣#xff08;LeetCode#xff09;
存在一个 无向图 #xff0c;图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph #xff0c;其中 graph[u] 是一个节点数组#xff0c;由节点 u 的邻接节点组成。形式上#xff0c…. - 力扣LeetCode
存在一个 无向图 图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph 其中 graph[u] 是一个节点数组由节点 u 的邻接节点组成。形式上对于 graph[u] 中的每个 v 都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性
不存在自环graph[u] 不包含 u。不存在平行边graph[u] 不包含重复值。如果 v 在 graph[u] 内那么 u 也应该在 graph[v] 内该图是无向图这个图可能不是连通图也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。
二分图 定义如果能将一个图的节点集合分割成两个独立的子集 A 和 B 并使图中的每一条边的两个节点一个来自 A 集合一个来自 B 集合就将这个图称为 二分图 。
如果图是二分图返回 true 否则返回 false 。 示例 1 输入graph [[1,2,3],[0,2],[0,1,3],[0,2]]
输出false
解释不能将节点分割成两个独立的子集以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。
示例 2 输入graph [[1,3],[0,2],[1,3],[0,2]]
输出true
解释可以将节点分成两组: {0, 2} 和 {1, 3} 。 提示
graph.length n1 n 1000 graph[u].length n0 graph[u][i] n - 1graph[u] 不会包含 ugraph[u] 的所有值 互不相同如果 graph[u] 包含 v那么 graph[v] 也会包含 u class Solution {
public:bool isBipartite(vectorvectorint graph) {unordered_setint a;unordered_setint b;for (int i 0; i graph.size(); i) {auto nodes graph[i];if (a.find(i) ! a.end()) {for (int j 0; j nodes.size(); j) {if (a.find(nodes[j]) ! a.end()) {return false;}if (b.find(nodes[j]) b.end()) {b.insert(nodes[j]);}} } else if (b.find(i) ! b.end()) {for (int j 0; j nodes.size(); j) {if (b.find(nodes[j]) ! b.end()) {return false;}if (a.find(nodes[j]) a.end()) {a.insert(nodes[j]);}}} else {a.insert(i);for (int j 0; j nodes.size(); j) {if (a.find(nodes[j]) ! a.end()) {return false;}if (b.find(nodes[j]) b.end()) {b.insert(nodes[j]);}}}}return true;}
};
class Solution {
public:bool isBipartite(vectorvectorint graph) {int n graph.size();vectorint flags(n, 0);for (int i 0; i n; i) {auto nodes graph[i];if (flags[i] -1) {// in Afor (int j 0; j nodes.size(); j) {if (flags[nodes[j]] -1) {// in Areturn false;}flags[nodes[j]] 1;// put in B}} else if (flags[i] 1) {// in Bfor (int j 0; j nodes.size(); j) {if (flags[nodes[j]] 1) {// in Breturn false;}flags[nodes[j]] -1;// put in A} } else {flags[i] -1;for (int j 0; j nodes.size(); j) {if (flags[nodes[j]] -1) {// in Areturn false;}flags[nodes[j]] 1;// put in B} }}return true;}
};
class Solution {
public:bool isBipartite(vectorvectorint graph) {int n graph.size();vectorint flags(n, 0);for (int i 0; i n; i) {if (flags[i] 0) {if (!isBipartite(i, 1, flags, graph)) {return false;}}}return true;}bool isBipartite(int curNode, int curFlag, vectorint flags, vectorvectorint graph) {if (flags[curNode] ! 0) {return flags[curNode] curFlag;}flags[curNode] curFlag;for (auto nextNode : graph[curNode]) {if (!isBipartite(nextNode, -curFlag, flags, graph)) {return false;}}return true;}
};
