We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Add Edges to Make Degrees of All Nodes Even

Number: 2596

Difficulty: Hard

Paid? No

Companies: Uber, Hudson River Trading

Problem Description

Given an undirected graph with n nodes (labeled from 1 to n) and a list of edges, determine if it is possible to add at most two new edges (without self-loops or duplicate edges) so that every node ends up with an even degree.

Key Insights

  • Only nodes with odd degree need to be “corrected” by adding edges.
  • With at most two extra edges, there can only be 0, 2, or 4 nodes with odd degree.
  • For 0 odd nodes, the graph already satisfies the requirements.
  • For 2 odd nodes, either a direct edge between them (if not already present) or a two-edge solution via an intermediate node is possible.
  • For 4 odd nodes, test all three possible pairings; each added edge must not be an existing edge.
  • If there are any other number of odd nodes you cannot fix the degrees with at most 2 extra edges.

Space and Time Complexity

Time Complexity: O(m + n) where m is the number of given edges and n is the number of nodes. In the worst-case (2 odd nodes) an extra O(n) loop is performed. Space Complexity: O(m + n) due to storage for the edge set and degree counter.

Solution

The solution first computes the degree of each node and records all edges in a set for constant time edge-existence checks. After identifying the nodes with odd degree, we branch into three cases:

  1. If there are no odd nodes, the answer is true.
  2. If there are exactly 2 odd nodes, try to add a direct edge between them if it doesn’t already exist. If it does exist, check if there is an intermediate node which can connect to both odd nodes with two new valid edges.
  3. If there are exactly 4 odd nodes, test all three possible pairings of these nodes. If any valid pairing exists (i.e. neither edge in the pair is already present), return true. If none of the above cases succeed, return false.

Data structures used include:

  • A set/hash table for quickly checking if an edge already exists.
  • A simple array or list for counting degrees. The algorithm leverages careful case analysis to decide the outcome with a constant number of trials when the odd nodes count is small.

Code Solutions

# Function to check if the graph can be fixed with at most 2 extra edges.
def isPossible(n, edges):
    # Create an edge set and degree counter for nodes 1 ... n.
    edge_set = set()
    degree = [0] * (n + 1)
    for u, v in edges:
        degree[u] += 1
        degree[v] += 1
        # Store edge in sorted order to avoid duplicate representations.
        edge_set.add((min(u, v), max(u, v)))
    
    # List nodes with odd degree.
    odds = [node for node in range(1, n + 1) if degree[node] % 2 == 1]
    
    # Helper: check if edge (u, v) exists.
    def exists(u, v):
        return (min(u, v), max(u, v)) in edge_set

    # If no odd nodes, no extra edge is needed.
    if len(odds) == 0:
        return True

    # Case with exactly 2 odd nodes.
    if len(odds) == 2:
        a, b = odds
        if not exists(a, b):
            # Directly adding edge between a and b fixes both.
            return True
        # Otherwise try finding an intermediate node x.
        for x in range(1, n + 1):
            if x == a or x == b:
                continue
            if not exists(a, x) and not exists(b, x):
                # Adding edges (a, x) and (b, x) fixes degrees.
                return True
        return False

    # Case with exactly 4 odd nodes.
    if len(odds) == 4:
        a, b, c, d = odds
        # Option 1: Pair (a,b) and (c,d)
        if not exists(a, b) and not exists(c, d):
            return True
        # Option 2: Pair (a,c) and (b,d)
        if not exists(a, c) and not exists(b, d):
            return True
        # Option 3: Pair (a,d) and (b,c)
        if not exists(a, d) and not exists(b, c):
            return True
        return False

    # More than 4 odd nodes cannot be fixed with at most 2 extra edges.
    return False

# Example usage:
# print(isPossible(5, [[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]))
← Back to All Questions