Untitled
unknown
c_cpp
2 years ago
1.3 kB
6
Indexable
//////////////// DFS APPROACH ////////////////////// public: bool isBipartite(vector<vector<int>>& adjList) { int n = adjList.size(); vector<int> color(n, 0); // color = 0 [uncolored], 1 [colored with Red], 2 [colored with blue] for (int i = 0; i < n; i++) { // cover all disconnected components if (color[i] == 0) { if (!dfsColor(i, color, adjList, 2)) return false; } } // all components can be colored. return true; } // check if component can be colored with 2 colors bool dfsColor(int node, vector<int> &color, vector<vector<int>> &adjList, int parentColor) { if (color[node] != 0) // if node already colored if (color[node] == parentColor) // if node's color same as parent color -> Not bipartite return false; else return true; // assign opposite color of parent color[node] = (parentColor == 1 ? 2 : 1); for (auto connNode : adjList[node]) { if (!dfsColor(connNode, color, adjList, color[node])) // if any of the path return NOT bipartite then return false and don't check any further. return false; } return true; }
Editor is loading...