Welcome to Subscribe On Youtube

886. Possible Bipartition

Description

We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people, and they should not go into the same group.

Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if it is possible to split everyone into two groups in this way.

 

Example 1:

Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: The first group has [1,4], and the second group has [2,3].

Example 2:

Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
Explanation: We need at least 3 groups to divide them. We cannot put them in two groups.

 

Constraints:

• 1 <= n <= 2000
• 0 <= dislikes.length <= 104
• dislikes[i].length == 2
• 1 <= ai < bi <= n
• All the pairs of dislikes are unique.

Solutions

Solution 1

Union find.

Solution 2

Union-find is a tree-shaped data structure. As the name suggests, it is used to deal with some disjoint merge and query problems. It supports two operations:

1. Find: Determine which subset an element is in, the time complexity of a single operation is $O(\alpha(n))$
2. Union: Merge two subsets into one set, the time complexity of a single operation is $O(\alpha(n))$

Among them, $\alpha$ is the inverse function of Ackerman function, and its growth is extremely slow, which means that the average running time of a single operation can be considered as a small constant.

The following are commonly used templates for union search, which require proficiency. Among them:

• n represents the number of nodes
• p stores the parent node of each point. Initially, the parent node of each point is itself.
• size is only meaningful when the node is an ancestor node, indicating the number of points in the set where the ancestor node is located
• The find(x) function is used to find the ancestor node of the set where $x$ is located
• The union(a, b) function is used to merge the collections where $a$ and $b$ are located

p = list(range(n))
size = [1] * n


def find(x):
    if p[x] != x:
        # 路径压缩
        p[x] = find(p[x])
    return p[x]


def union(a, b):
    pa, pb = find(a), find(b)
    if pa == pb:
        return
    p[pa] = pb
    size[pb] += size[pa]

For this question, we traverse each person. He and the person he dislikes should not be in the same set. If they are in the same set, a conflict will occur and false will be returned directly. If there are no conflicts, then merge all his disliked ones into the same set.

The traversal ends, indicating that there is no conflict, and true is returned.

Time complexity $O(n + m\times \alpha(n))$.

Solution 3: Explicit-Stack Coloring

Thinking

People who dislike each other cannot share a group, so the dislike graph must be bipartite. With $n\le 2000$, recursion along a chain of dislikes uses a call depth equal to the number of people and overflows Python once the chain reaches length $1000$. A graph is bipartite exactly when two colors can cover it with every edge joining different colors. A stack therefore expands each component: an uncolored person is colored $1$ and pushed, a popped person fails the search when a neighbor already has the same color, and an uncolored neighbor is colored $3$ minus the current color and pushed. A partition exists when every component is colored.

• Java
• C++
• Python
• Go
• TypeScript
• Rust

• class Solution {
      private int[] p;
  
      public boolean possibleBipartition(int n, int[][] dislikes) {
          p = new int[n];
          List<Integer>[] g = new List[n];
          Arrays.setAll(g, k -> new ArrayList<>());
          for (int i = 0; i < n; ++i) {
              p[i] = i;
          }
          for (var e : dislikes) {
              int a = e[0] - 1, b = e[1] - 1;
              g[a].add(b);
              g[b].add(a);
          }
          for (int i = 0; i < n; ++i) {
              for (int j : g[i]) {
                  if (find(i) == find(j)) {
                      return false;
                  }
                  p[find(j)] = find(g[i].get(0));
              }
          }
          return true;
      }
  
      private int find(int x) {
          if (p[x] != x) {
              p[x] = find(p[x]);
          }
          return p[x];
      }
  }
  
  
  // Solution 2
  class Solution {
      private int[] p;
  
      public boolean possibleBipartition(int n, int[][] dislikes) {
          p = new int[n];
          List<Integer>[] g = new List[n];
          Arrays.setAll(g, k -> new ArrayList<>());
          for (int i = 0; i < n; ++i) {
              p[i] = i;
          }
          for (var e : dislikes) {
              int a = e[0] - 1, b = e[1] - 1;
              g[a].add(b);
              g[b].add(a);
          }
          for (int i = 0; i < n; ++i) {
              for (int j : g[i]) {
                  if (find(i) == find(j)) {
                      return false;
                  }
                  p[find(j)] = find(g[i].get(0));
              }
          }
          return true;
      }
  
      private int find(int x) {
          if (p[x] != x) {
              p[x] = find(p[x]);
          }
          return p[x];
      }
  }
  
  
  
  // Solution 3
  class Solution {
      public boolean possibleBipartition(int n, int[][] dislikes) {
          List<Integer>[] g = new List[n];
          Arrays.setAll(g, k -> new ArrayList<>());
          for (var e : dislikes) {
              int a = e[0] - 1, b = e[1] - 1;
              g[a].add(b);
              g[b].add(a);
          }
          int[] color = new int[n];
          for (int start = 0; start < n; ++start) {
              if (color[start] != 0) {
                  continue;
              }
              color[start] = 1;
              Deque<Integer> stk = new ArrayDeque<>();
              stk.push(start);
              while (!stk.isEmpty()) {
                  int i = stk.pop();
                  for (int j : g[i]) {
                      if (color[j] == color[i]) {
                          return false;
                      }
                      if (color[j] == 0) {
                          color[j] = 3 - color[i];
                          stk.push(j);
                      }
                  }
              }
          }
          return true;
      }
  }
  
  

• class Solution {
  public:
      bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
          vector<int> p(n);
          iota(p.begin(), p.end(), 0);
          unordered_map<int, vector<int>> g;
          for (auto& e : dislikes) {
              int a = e[0] - 1, b = e[1] - 1;
              g[a].push_back(b);
              g[b].push_back(a);
          }
          function<int(int)> find = [&](int x) -> int {
              if (p[x] != x) p[x] = find(p[x]);
              return p[x];
          };
          for (int i = 0; i < n; ++i) {
              for (int j : g[i]) {
                  if (find(i) == find(j)) return false;
                  p[find(j)] = find(g[i][0]);
              }
          }
          return true;
      }
  };
  
  
  // Solution 2
  class Solution {
  public:
      bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
          vector<int> p(n);
          iota(p.begin(), p.end(), 0);
          unordered_map<int, vector<int>> g;
          for (auto& e : dislikes) {
              int a = e[0] - 1, b = e[1] - 1;
              g[a].push_back(b);
              g[b].push_back(a);
          }
          function<int(int)> find = [&](int x) -> int {
              if (p[x] != x) p[x] = find(p[x]);
              return p[x];
          };
          for (int i = 0; i < n; ++i) {
              for (int j : g[i]) {
                  if (find(i) == find(j)) return false;
                  p[find(j)] = find(g[i][0]);
              }
          }
          return true;
      }
  };
  
  
  
  // Solution 3
  class Solution {
  public:
      bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
          vector<vector<int>> g(n);
          for (auto& e : dislikes) {
              int a = e[0] - 1, b = e[1] - 1;
              g[a].push_back(b);
              g[b].push_back(a);
          }
          vector<int> color(n);
          for (int start = 0; start < n; ++start) {
              if (color[start]) {
                  continue;
              }
              color[start] = 1;
              vector<int> stk{start};
              while (!stk.empty()) {
                  int i = stk.back();
                  stk.pop_back();
                  for (int j : g[i]) {
                      if (color[j] == color[i]) {
                          return false;
                      }
                      if (color[j] == 0) {
                          color[j] = 3 - color[i];
                          stk.push_back(j);
                      }
                  }
              }
          }
          return true;
      }
  };
  
  

• class Solution:
      def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
          def find(x):
              if p[x] != x:
                  p[x] = find(p[x])
              return p[x]
  
          g = defaultdict(list)
          for a, b in dislikes:
              a, b = a - 1, b - 1
              g[a].append(b)
              g[b].append(a)
          p = list(range(n))
          for i in range(n):
              for j in g[i]:
                  if find(i) == find(j):
                      return False
                  p[find(j)] = find(g[i][0])
          return True
  
  
  # Solution 2
  class Solution:
      def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
          def find(x):
              if p[x] != x:
                  p[x] = find(p[x])
              return p[x]
  
          g = defaultdict(list)
          for a, b in dislikes:
              a, b = a - 1, b - 1
              g[a].append(b)
              g[b].append(a)
          p = list(range(n))
          for i in range(n):
              for j in g[i]:
                  if find(i) == find(j):
                      return False
                  p[find(j)] = find(g[i][0])
          return True
  
  
  
  # Solution 3
  class Solution:
      def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
          g = defaultdict(list)
          for a, b in dislikes:
              a, b = a - 1, b - 1
              g[a].append(b)
              g[b].append(a)
          color = [0] * n
          for start in range(n):
              if color[start]:
                  continue
              color[start] = 1
              stk = [start]
              while stk:
                  i = stk.pop()
                  for j in g[i]:
                      if color[j] == color[i]:
                          return False
                      if color[j] == 0:
                          color[j] = 3 - color[i]
                          stk.append(j)
          return True
  
  

• func possibleBipartition(n int, dislikes [][]int) bool {
  	p := make([]int, n)
  	g := make([][]int, n)
  	for i := range p {
  		p[i] = i
  	}
  	for _, e := range dislikes {
  		a, b := e[0]-1, e[1]-1
  		g[a] = append(g[a], b)
  		g[b] = append(g[b], a)
  	}
  	var find func(int) int
  	find = func(x int) int {
  		if p[x] != x {
  			p[x] = find(p[x])
  		}
  		return p[x]
  	}
  	for i := 0; i < n; i++ {
  		for _, j := range g[i] {
  			if find(i) == find(j) {
  				return false
  			}
  			p[find(j)] = find(g[i][0])
  		}
  	}
  	return true
  }
  
  
  // Solution 2
  func possibleBipartition(n int, dislikes [][]int) bool {
  	p := make([]int, n)
  	g := make([][]int, n)
  	for i := range p {
  		p[i] = i
  	}
  	for _, e := range dislikes {
  		a, b := e[0]-1, e[1]-1
  		g[a] = append(g[a], b)
  		g[b] = append(g[b], a)
  	}
  	var find func(int) int
  	find = func(x int) int {
  		if p[x] != x {
  			p[x] = find(p[x])
  		}
  		return p[x]
  	}
  	for i := 0; i < n; i++ {
  		for _, j := range g[i] {
  			if find(i) == find(j) {
  				return false
  			}
  			p[find(j)] = find(g[i][0])
  		}
  	}
  	return true
  }
  
  
  
  // Solution 3
  func possibleBipartition(n int, dislikes [][]int) bool {
  	g := make([][]int, n)
  	for _, e := range dislikes {
  		a, b := e[0]-1, e[1]-1
  		g[a] = append(g[a], b)
  		g[b] = append(g[b], a)
  	}
  	color := make([]int, n)
  	for start := 0; start < n; start++ {
  		if color[start] != 0 {
  			continue
  		}
  		color[start] = 1
  		stk := []int{start}
  		for len(stk) > 0 {
  			i := stk[len(stk)-1]
  			stk = stk[:len(stk)-1]
  			for _, j := range g[i] {
  				if color[j] == color[i] {
  					return false
  				}
  				if color[j] == 0 {
  					color[j] = 3 - color[i]
  					stk = append(stk, j)
  				}
  			}
  		}
  	}
  	return true
  }
  
  

• function possibleBipartition(n: number, dislikes: number[][]): boolean {
      const color = new Array(n + 1).fill(0);
      const g = Array.from({ length: n + 1 }, () => []);
      const dfs = (i: number, v: number) => {
          color[i] = v;
          for (const j of g[i]) {
              if (color[j] === color[i] || (color[j] === 0 && dfs(j, 3 ^ v))) {
                  return true;
              }
          }
          return false;
      };
      for (const [a, b] of dislikes) {
          g[a].push(b);
          g[b].push(a);
      }
      for (let i = 1; i <= n; i++) {
          if (color[i] === 0 && dfs(i, 1)) {
              return false;
          }
      }
      return true;
  }
  
  
  
  // Solution 3
  function possibleBipartition(n: number, dislikes: number[][]): boolean {
      const g: number[][] = Array.from({ length: n }, () => []);
      for (const [a, b] of dislikes) {
          g[a - 1].push(b - 1);
          g[b - 1].push(a - 1);
      }
      const color: number[] = new Array(n).fill(0);
      for (let start = 0; start < n; start++) {
          if (color[start] !== 0) {
              continue;
          }
          color[start] = 1;
          const stk: number[] = [start];
          while (stk.length) {
              const i = stk.pop()!;
              for (const j of g[i]) {
                  if (color[j] === color[i]) {
                      return false;
                  }
                  if (color[j] === 0) {
                      color[j] = 3 - color[i];
                      stk.push(j);
                  }
              }
          }
      }
      return true;
  }
  
  

• impl Solution {
      fn dfs(i: usize, v: usize, color: &mut Vec<usize>, g: &Vec<Vec<usize>>) -> bool {
          color[i] = v;
          for &j in (*g[i]).iter() {
              if color[j] == color[i] || (color[j] == 0 && Self::dfs(j, v ^ 3, color, g)) {
                  return true;
              }
          }
          false
      }
  
      pub fn possible_bipartition(n: i32, dislikes: Vec<Vec<i32>>) -> bool {
          let n = n as usize;
          let mut color = vec![0; n + 1];
          let mut g = vec![Vec::new(); n + 1];
          for d in dislikes.iter() {
              let (i, j) = (d[0] as usize, d[1] as usize);
              g[i].push(j);
              g[j].push(i);
          }
          for i in 1..=n {
              if color[i] == 0 && Self::dfs(i, 1, &mut color, &g) {
                  return false;
              }
          }
          true
      }
  }
  
  
  
  // Solution 3
  impl Solution {
      pub fn possible_bipartition(n: i32, dislikes: Vec<Vec<i32>>) -> bool {
          let n = n as usize;
          let mut g = vec![Vec::new(); n];
          for d in dislikes.iter() {
              let a = d[0] as usize - 1;
              let b = d[1] as usize - 1;
              g[a].push(b);
              g[b].push(a);
          }
          let mut color = vec![0; n];
          for start in 0..n {
              if color[start] != 0 {
                  continue;
              }
              color[start] = 1;
              let mut stk = vec![start];
              while let Some(i) = stk.pop() {
                  for &j in &g[i] {
                      if color[j] == color[i] {
                          return false;
                      }
                      if color[j] == 0 {
                          color[j] = 3 - color[i];
                          stk.push(j);
                      }
                  }
              }
          }
          true
      }
  }
  
  

All Problems

All Solutions