Bipartite Graph Validation

Determine if a given network of friends can be divided into two groups where no friends in the same group are directly connected. This problem tests graph traversal and coloring skills, crucial for understanding network structures and resource allocation.

graphbipartitegraph-coloringdepth-first-search

Problem Statement

Imagine a social network represented as a graph. Each person is a node, and friendships are represented as edges. Your task is to determine if this network can be split into two distinct groups such that no two people in the same group are friends. In other words, can you color the graph with two colors such that no two adjacent nodes share the same color?

Example 1

Input: [[1, 2], [0, 2], [0, 1, 3], [2]]

Output: True

This graph can be divided into two groups: {0, 3} and {1, 2}. No individuals within the same group are friends.

Example 2

Input: [[1, 3], [0, 2], [1, 3], [0, 2]]

Output: False

This graph cannot be divided into two groups where no friends are in the same group. For example, if 0 and 1 are in different groups, then 2 must be in the same group as 0 and 3 must be in the same group as 1, creating a conflict.

Constraints

-The graph is undirected.
-The graph may not be fully connected.
-The number of nodes in the graph will be between 1 and 1000.
-Each node's adjacency list will contain unique nodes.
-There will be no self-loops (an edge from a node to itself).

Brute Force Approach

Imagine trying every possible grouping of people. For each grouping, you'd check if any friends ended up in the same group. This is like trying every combination of assigning people to two teams and checking if any teammates are friends. This approach is incredibly inefficient because the number of possible groupings grows exponentially with the number of people.

TimeO(2^n * m)

SpaceO(n)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem