Skip to content
TheChatArchiveThe Chat Archive
GLMGLM-5 / Pony Alpha· unknownHugging Face Frontier Reasoning Traces

Write a program that checks if a graph is bipartite.

  1. User

    Write a program that checks if a graph is bipartite.

  2. GLM Assistant

    The user wants a program to check if a graph is bipartite.

    1. Understand the concept of a Bipartite Graph:

    • A graph is bipartite if its vertices can be divided into two disjoint and independent sets UU and VV such that every edge connects a vertex in UU to one in VV.
    • Equivalently, a graph is bipartite if and only if it is 2-colorable (e.g., can be colored with two colors such that no adjacent nodes share the same color).
    • Equivalently, a graph is bipartite if and only if it contains no odd-length cycles.

    2. Choose the Algorithm: The most common and efficient way to check for bipartiteness is using Breadth-First Search (BFS) or Depth-First Search (DFS).

    • Algorithm (BFS approach):
      1. Assign a color (say, 1) to the source node.
      2. Assign the opposite color (say, -1) to all its neighbors.
      3. Repeat recursively (iteratively using a queue) for all neighbors.
      4. If we encounter a node that is already colored and has the same color as its neighbor, the graph is not bipartite.
      5. Since the graph might be disconnected, we need to run this check for every unvisited component.

    3. Select the Programming Language: Python is generally the most accessible language for algorithmic examples due to its readability. I should probably provide a Python solution, but maybe offer C++ or Java as well if requested. Since the prompt is generic ("Write a program"), Python is the safest default choice. I will write the solution in Python.

    4. Draft the Code Structure (Python):

    • Input: An adjacency list representing the graph. Let's say graph is a dictionary or a list of lists where graph[u] contains neighbors of u.
    • Data Structure: An array or dictionary colors to store the state of each node (-1, 0, 1). 0 means uncolored/visited. 1 and -1 are the two colors.
    • Function: is_bipartite(graph)

    5. Refine the Code Logic:

    def is_bipartite(graph):
        n = len(graph) # Number of nodes
        colors = [0] * n # 0: uncolored, 1: color A, -1: color B
    
        # Iterate through all nodes to handle disconnected components
        for i in range(n):
            if colors[i] != 0:
                continue # Already visited
    
            # Start BFS
            queue = [i]
            colors[i] = 1 # Assign first color
    
            while queue:
                curr = queue.pop(0)
    
                for neighbor in graph[curr]:
                    if colors[neighbor] == 0:
                        # Color with opposite color
                        colors[neighbor] = -colors[curr]
                        queue.append(neighbor)
                    elif colors[neighbor] == colors[curr]:
                        # Same color neighbor -> Not bipartite
                        return False
        return True
    

    6. Handling Input Formats: The user didn't specify the input format.

    • Format A (Adjacency List): [[1,3], [0,2], [1,3], [0,2]]
    • Format B (Edge List): [(0,1), (1,2), ...]
    • Format C (Adjacency Matrix): [[0,1...], [1,0...]]

    I will stick to the Adjacency List as it's the standard for graph traversal problems. I'll provide a complete runnable example including a main block to demonstrate usage.

    7. Edge Cases:

    • Empty graph: Trivially bipartite. The loop range(0) won't run, returns True.
    • Single node: Bipartite. Colors[0] becomes 1, queue empty, returns True.
    • Disconnected graph: The outer loop handles this.

    8. Alternative Implementation (DFS): DFS is often cleaner to write recursively, but iterative BFS is easier to explain conceptually for "layers" of coloring. I'll stick with BFS but maybe mention DFS works too. Actually, let's stick to BFS as the primary solution because checking cycles usually implies level-order logic in tutorials.

    9. Constructing the Explanation:

    • Define what Bipartite means (2-colorable).
    • Explain the BFS approach.
    • Provide the code.
    • Explain the code logic (initialization, outer loop for components, inner loop for traversal, conflict check).
    • Provide example inputs (one bipartite, one not).

    10. Refining the Code for "Production" Quality:

    • Use collections.deque for efficient popping from the front in Python.
    • Add comments.
    • Make the graph size explicit.

    Let's write the actual response.

    • Language: Python 3.
    • Approach: BFS 2-coloring.
    • Code:
      • Define is_bipartite(n, edges) or is_bipartite(graph). Let's assume the input is an adjacency list for simplicity, or provide a conversion. Providing the adjacency list directly is best for algorithmic clarity.

    Let's double check the logic for a simple triangle (0-1, 1-2, 2-0).

    • Start 0 -> color 1. Queue: [0]
    • Pop 0. Neighbors 1, 2.
      • Neighbor 1 -> color -1. Queue: [1]
      • Neighbor 2 -> color -1. Queue: [1, 2]
    • Pop 1. Neighbors 0, 2.
      • Neighbor 0 is color 1. 1 != -1. OK.
      • Neighbor 2 is color -1. -1 == -1. Conflict! Return False.
      • Correct.

    Logic for a line (0-1, 1-2).

    • Start 0 -> color 1. Queue: [0]
    • Pop 0. Neighbor 1.
      • Neighbor 1 -> color -1. Queue: [1]
    • Pop 1. Neighbors 0, 2.
      • Neighbor 0 color 1 != -1.
      • Neighbor 2 uncolored -> color 1. Queue: [2]
    • Pop 2. Neighbor 1 color -1 != 1.
    • Queue empty. Return True. Correct.

    Final Output Structure:

    1. Brief explanation of the logic (BFS + 2 colors).
    2. Python Code.
    3. Example usage.
    4. Time/Space complexity analysis.

    I should also consider writing it in C++ or Java just in case, but usually, one language is sufficient unless specified. I will provide Python as the primary answer.

    Wait, what if the graph input is just edges? I will assume the input is an Adjacency List because it's the most efficient representation for this algorithm.

    Let's add a small note about the input format.

    Code:

    from collections import deque
    
    def is_bipartite(graph):
        """
        Checks if a graph is bipartite using BFS (Breadth-First Search).
        A graph is bipartite if its vertices can be divided into two disjoint sets
        such that every edge connects a vertex in one set to a vertex in the other.
        """
        n = len(graph)
        # 0: Uncolored, 1: Red, -1: Blue
        colors = [0] * n
    
        # Loop through all nodes to handle disconnected graphs
        for i in range(n):
            if colors[i] != 0:
                continue
    
            # Start BFS
            queue = deque([i])
            colors[i] = 1  # Assign first color
    
            while queue:
                node = queue.popleft()
    
                for neighbor in graph[node]:
                    if colors[neighbor] == 0:
                        # If neighbor is not colored, color with opposite color
                        colors[neighbor] = -colors[node]
                        queue.append(neighbor)
                    elif colors[neighbor] == colors[node]:
                        # If neighbor has same color, graph is not bipartite
                        return False
    
        return True
    

    This looks solid. I will format this nicely.

    One small detail: Should I support an adjacency matrix? No, usually "graph" implies adjacency list in competitive programming/interview contexts unless specified. I'll stick to the list.

    Complexity: Time: O(V + E) - standard BFS. Space: O(V) - for color array and queue.

    I'll write the response now. Here is a Python program to check if a graph is bipartite.

    The Logic

    A graph is bipartite if its vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other.

    The standard way to check this is using Breadth-First Search (BFS) (or DFS) to try and 2-color the graph:

    1. Assign a color (e.g., Red/1) to the source node.
    2. Assign the opposite color (e.g., Blue/-1) to all its neighbors.
    3. Repeat for all neighbors.
    4. If you encounter an edge that connects two nodes of the same color, the graph is not bipartite.
    5. If you finish coloring without conflicts, the graph is bipartite.

    The Code (Python)

    from collections import deque
    
    def is_bipartite(graph):
        """
        Checks if a graph is bipartite using BFS.
        
        Args:
            graph (dict or list): Adjacency list representation of the graph.
                                  Example: {0: [1, 3], 1: [0, 2], ...}
                                  
        Returns:
            bool: True if bipartite, False otherwise.
        """
        
        # Determine the number of nodes. 
        # Handles both dictionary input {0:[...], 1:[...]} and list of lists [[...], [...]]
        if isinstance(graph, dict):
            nodes = list(graph.keys())
        else:
            nodes = range(len(graph))
            
        # Dictionary to store colors. 
        # 1 = Group A, -1 = Group B, None = Uncolored
        colors = {node: None for node in nodes}
        
        # We iterate through all nodes because the graph might be disconnected
        for start_node in nodes:
            # If the node is already colored, we've processed its component
            if colors[start_node] is not None:
                continue
            
            # Start BFS for this component
            queue = deque([start_node])
            colors[start_node] = 1  # Assign initial color
            
            while queue:
                current = queue.popleft()
                
                for neighbor in graph[current]:
                    # If neighbor is not colored, color it opposite to current
                    if colors[neighbor] is None:
                        colors[neighbor] = -colors[current]
                        queue.append(neighbor)
                    
                    # If neighbor has the SAME color as current, conflict found!
                    elif colors[neighbor] == colors[current]:
                        return False
                        
        return True
    
    # --- Usage Examples ---
    
    if __name__ == "__main__":
        # Example 1: A Bipartite Graph (Square 0-1-2-3-0)
        # 0 -- 1
        # |    |
        # 3 -- 2
        bipartite_graph = {
            0: [1, 3],
            1: [0, 2],
            2: [1, 3],
            3: [0, 2]
        }
    
        # Example 2: A Non-Bipartite Graph (Triangle 0-1-2-0)
        # Odd cycles are never bipartite
        non_bipartite_graph = {
            0: [1, 2],
            1: [0, 2],
            2: [0, 1]
        }
    
        print(f"Graph 1 is bipartite: {is_bipartite(bipartite_graph)}")       # Output: True
        print(f"Graph 2 is bipartite: {is_bipartite(non_bipartite_graph)}")   # Output: False
    

    Complexity Analysis

    • Time Complexity: O(V+E)O(V + E), where VV is the number of vertices and EE is the number of edges. We visit every node and every edge exactly once.
    • Space Complexity: O(V)O(V), to store the colors dictionary and the BFS queue.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.