The O(n) Club: Possible Bipartition: Or, How to Split Your Frenemies into Two Drama-Free Camps
The O(n) Club: Possible Bipartition: Or, How to Split Your Frenemies into Two Drama-Free Camps
dgtalbug
- 2 min read

The O(n) Club: Possible Bipartition: Or, How to Split Your Frenemies into Two Drama-Free Camps

On this page
Introduction

The O(n) Club: Possible Bipartition — Or, How to Split Your Frenemies into Two Drama-Free Camps

⚡ TL;DR

Split n people into two teams, so no sworn enemies end up on the same side—a classic case of coloring a graph and hoping you don’t see a triangle. The quick and dirty with Java:

🧠 How Devs Usually Mess This Up

Ah, the classics:

🔍 What’s Actually Going On

This is the anti-drama club algorithm: People are nodes, dislikes are edgy edges. If you can pick two colors so neighbors never clash, congrats: your graph (and friend group) is bipartite and peace reigns (for now).

When you (literally) can’t, it’s probably thanks to an odd-length cycle—think three folks with mutual beef. That’s a triangle of doom that breaks two-color harmony.

🛠️ PseudoCode

Step 4: Check every node because cliques can be sneaky.

for (int i = 1; i <= n; i++) {
  if (color[i] == 0 && !dfs(i, 1)) return false;
}

Nobody gets left uncolored, not even the quiet ones.

Step 3: For every uncolored soul, paint with DFS.

boolean dfs(int node, int paint) {
  color[node] = paint;
  for (int neighbor : graph[node]) {
    if (color[neighbor] == 0) {
      if (!dfs(neighbor, -paint)) return false;
    } else if (color[neighbor] == paint) {
      return false;
    }
  }
  return true;
}

If you clash colors with a neighbor—run for the hills (or just return false, whatever works).

Step 2: Create a color array for people (0 for unpainted, 1/-1 for club t-shirts).

int[] color = new int[n + 1];

Yup, index from 1 to match the people labels. Nobody likes an off-by-one bug at a party.

Step 1: Build the adjacency list. Dislike is mutual, so add both ways.

for each [a, b] in dislikes:
  graph[a].add(b);
  graph[b].add(a);

No silent beef—everyone’s angst gets shared equally.

💻 The Code

public boolean possibleBipartition(int n, int[][] dislikes) {
    List&lt;Integer&gt;[] graph = new ArrayList[n + 1];
    for (int i = 1; i &lt;= n; i++) graph[i] = new ArrayList&lt;&gt;();
    for (int[] pair : dislikes) {
        graph[pair[0]].add(pair[1]);
        graph[pair[1]].add(pair[0]);
    }
    int[] color = new int[n + 1];
    for (int i = 1; i &lt;= n; i++) {
        if (color[i] == 0 &amp;&amp; !dfs(graph, color, i, 1)) return false;
    }
    return true;
}
 private boolean dfs(List&lt;Integer&gt;[] graph, int[] color, int node, int paint) {
    color[node] = paint;
    for (int neighbor : graph[node]) {
        if (color[neighbor] == 0) {
            if (!dfs(graph, color, neighbor, -paint)) return false;
        } else if (color[neighbor] == paint) {
            return false;
        }
    }
    return true;
}

⚠️ Pitfalls, Traps & Runtime Smacks

  • Watch out for odd cycles—like a feuding trio. You can’t split them with only two sides.
  • Your graph might be many islands (a.k.a. groups)—check them all or miss the introverts’ problems.
  • Mind the indexes! Use n+1 for 1-based nodes or you’ll paint outside the lines (and your heap).
  • O(n + e) and that’s it. Space and time—with DFS, code and coffee survive the largest drama club.

🧠 Interviewer Brain-Tattoo

“If your haters form an odd cycle, toss the paint brush and just split snacks instead.”

The O(n) Club Depth-First Search Breadth-First Search Union Find Graph