💻
Algorithm
  • README
  • Array
    • At Most To Equal
    • Count Inversions In An Array
    • Interleaving Placement
    • Kadane
    • Left To Right State Transition
    • Permutation
    • Quick Select
    • Sliding Window
    • Two Pointers
  • Binary Tree
    • Avl Tree
    • Binary Search Tree
    • Serialization And Deserialization
    • Traversal
  • Company
    • Facebook
  • Cpp
    • Array
    • Memset 3 F
    • Overflow
  • Data Structure
    • Binary Indexed Tree
    • Segment Tree And Binary Index Tree
    • Segment Tree
    • Stack
    • Trie
    • Union Find
  • Dynamic Programming
    • Knapsack
      • 0 1 Knapsack
      • Bounded Knapsack
      • Unbounded Knapsack
    • Bitmask Dp
    • Dp On Subsets
    • Dp On Tree
    • Dp With Sorting
    • Selective State Dp
    • Travelling Salesperson
  • Graph
    • Minimum Spanning Tree
      • Kruskal
      • Prim
    • Shortest Path
      • Bellman Ford
      • Dijkstra
      • Floyd Warshall
      • Johnson
      • Shortest Path Faster Algorithm
    • Bi Directional Breadth First Search
    • Bipartite
    • Breadth First Search
    • Component Coloring
    • Component Count
    • Depth First Search
    • Eulerian Path
    • Maximum Bipartite Matching
    • Tarjan
    • Topological Sort
    • Tree Diameter
    • Tree Ring Order Traversal
  • Greedy
    • Greedy Scheduling
    • Regret Greedy
  • Math
    • Catalan Number
    • Combinatorics
    • Factorial
    • Factorization
    • Fast Pow
    • Gcd
    • Geometry
    • Get Digits
    • Lcm
    • Median Minimizes Sum Of Absolute Deviations
    • Mode
    • Modular Multiplicative Inverse
    • Palindrome
    • Prime Number
    • Round Up
    • Sieve Of Eratosthenes
    • Stars And Bars
    • Sum Of Sequence
  • Miscellaneous
    • Bin Packing
    • Floyds Tortoise And Hare
    • Hungarian
    • Palindrome
  • Sort
    • Bubble Sort
    • Cycle Sort
    • Heap Sort
    • Merge Sort
    • Quick Sort
    • Sorting
  • Stl
    • Cpp Stl
    • Istringstream
    • Lower Bound Upper Bound
    • Priority Queue
  • String
    • Kmp
    • Manacher
    • Rabin Karp
    • String Processing
    • Z
  • Backtracking
  • Binary Answer
  • Binary Lifting
  • Binary Search
  • Bit Manipulation
  • Date
  • Difference Array
  • Discretization
  • Divide And Conquer
  • Gray Code
  • Great Problems For Practice
  • Interval Scheduling Maximization
  • Io Optimization
  • K Subset Partitioning
  • Line Sweep
  • Longest Common Subsequence
  • Longest Increasing Subsequence
  • Meet In The Middle
  • Minmax
  • Mono Deque
  • Monotonic Stack
  • Offline Query
  • P And Np
  • Prefix State Map
  • Prefix Sum
  • Random
  • Reservoir Sampling
  • Reverse Polish Notation
  • Sqrt Decomposition
Powered by GitBook
On this page
  • Is graph bipartite?
  • DFS
  • BFS
  • Problems

Was this helpful?

  1. Graph

Bipartite

PreviousBi Directional Breadth First SearchNextBreadth First Search

Last updated 3 years ago

Was this helpful?

A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

Bipartite

Is graph bipartite?

DFS

DFS to jump between two parts and assign part number to nodes

Take each node in the Graph as starting point of DFS.

Assign the nodes to one of two parts, -1 and 1, in an alternating order.

If a node is already assigned to a part, once it's visited again, its part should be the same as the part of the previous node.

// OJ: https://leetcode.com/problems/is-graph-bipartite/
// Author: github.com/lzl124631x
// Time: O(V + E)
// Space: O(V + E)
class Solution {
public:
    bool isBipartite(vector<vector<int>>& G) {
        vector<int> id(G.size());
        function<bool(int, int)> dfs = [&](int u, int prev) {
            if (id[u]) return id[u] != prev; // This node's part should be the same as the part of the previous part
            id[u] = -prev; // Assign nodes to one of the two parts, -1 or 1
            for (int v : G[u]) {
                if (!dfs(v, id[u])) return false;
            }
            return true;
        };
        for (int i = 0; i < G.size(); ++i) {
            if (id[i]) continue; // This node is already assigned to a part
            if (!dfs(i, 1)) return false;
        }
        return true;
    }
};

BFS

Take each node in the Graph as starting point of BFS.

Assign nodes to part -1 or 1 layer by layer in an alternating order.

If a node is already assigned to a part, once it's visited again, its part should be the same as the part of the previous node.

// OJ: https://leetcode.com/problems/is-graph-bipartite/
// Author: github.com/lzl124631x
// Time: O(V + E)
// Space: O(V + E)
class Solution {
public:
    bool isBipartite(vector<vector<int>>& G) {
        vector<int> id(G.size());
        queue<int> q;
        for (int i = 0; i < G.size(); ++i) {
            if (id[i]) continue; // This node is already assigned to a part
            q.push(i);
            id[i] = 1; // Assign this starting node to part 1
            while (q.size()) {
                int u = q.front();
                q.pop();
                for (int v : G[u]) {
                    if (id[v]) {
                        if (id[v] != -id[u]) return false; // Two neighboring nodes shouldn't be in the same part
                        continue;
                    }
                    id[v] = -id[u]; // Assign neighbor node to the other part
                    q.push(v);
                }
            }
        }
        return true;
    }
};

Problems

785. Is Graph Bipartite? (Medium)
785. Is Graph Bipartite? (Medium)
886. Possible Bipartition (Medium)