Problem Statement

Given an integer M and an undirected graph with N vertices and E edges. The goal is to determine whether the graph can be colored with a maximum of M colors so that no two of its adjacent vertices have the same color applied to them.

In this context, coloring a graph refers to giving each vertex a different color. If the coloring of vertices is possible then return true, otherwise return false.

Examples

Example 1:

Input: N = 4, M = 3, E = 5, Edges = [ 
                                     (0, 1),
                                     (1, 2),
                                     (2, 3),
                                     (3, 0),
                                     (0, 2)
                                    ]
Output: true

Explanation : Consider the three colors to be red, green, blue.
We can color the vertex 0 with red, vertex 1 with blue, vertex 2 with green, vertex 3 with blue.
In this way we can color graph using 3 colors at most.

Example 2:

Input: N = 3, M = 2, E = 3, Edges = [
                                     (0, 1),
                                     (1, 2),
                                     (0, 2)
                                    ]

Output: false

Explanation : Consider the three colors to be red, green.
We can color the vertex 0 with red, vertex 1 with blue.
As the vertex 2 is adjacent to both vertex 1 and 0 , so we cannot color with red and green.
Hence as we could not color all vertex of graph we return false.

Different Approaches

1️⃣ Backtracking

Real-Life Problem Solving:

Consider a scenario where several tasks need to be scheduled, each task requiring a specific resource. The objective is to assign resources to tasks such that no two tasks requiring the same resource are scheduled simultaneously. This is akin to assigning colors to nodes in a graph, where no two adjacent nodes (tasks) share the same color (resource). The challenge is to determine if it's possible to schedule all tasks using a limited number of resources.

Recursion Process Intuition:

Imagine attempting to assign a color to a node in a graph, starting from the first node and moving sequentially. For each node, every possible color is tried, ensuring it does not conflict with already colored adjacent nodes. If a valid color is found, the process moves to the next node. If a conflict arises, the current assignment is undone (backtracked), and the next color is attempted. This recursive process continues until all nodes are successfully colored or all possibilities are exhausted, indicating no valid coloring exists.

Approach:

1. Represent the graph using an adjacency list for efficient traversal and initialize a colors array to keep track of the assigned colors for each node, starting with no colors assigned.
2. Define a function to check if it's safe to assign a specific color to a node by ensuring no adjacent node has the same color.
3. Implement a recursive function to attempt to color each node:
   1. If all nodes are successfully colored, return true.
   2. For the current node, try all possible colors from 1 to m.
   3. Check if assigning a color is safe using the helper function.
   4. If safe, assign the color and recursively attempt to color the next node.
   5. If coloring the next node fails, reset the current node's color and try the next color.
   6. If no valid color is found, return false.
4. Start the coloring process from the first node and continue recursively until all nodes are processed. The result of the recursive function indicates whether the graph can be colored with the given number of colors.

Code:

 class Solution {
public:
    // Helper function to check if it's safe to assign `colorToAssign` to the `currentNode`
    bool isSafe(int colorToAssign, int currentNode, vector<int>& nodeColors, vector<int> adjacencyList[]) {
        for (int neighbor : adjacencyList[currentNode]) {
            // If any adjacent node already has the same color, it's not safe
            if (nodeColors[neighbor] == colorToAssign) {
                return false;
            }
        }
        return true; // Safe to color
    }

    // Recursive backtracking function to try coloring each node
    bool tryColoringGraph(int currentNode, int maxColors, int totalNodes, vector<int>& nodeColors, vector<int> adjacencyList[]) {
        // Base case: All nodes have been successfully colored
        if (currentNode == totalNodes) {
            return true;
        }

        // Try assigning each color from 1 to maxColors
        for (int color = 1; color <= maxColors; color++) {
            // Check if it's safe to assign this color to the current node
            if (isSafe(color, currentNode, nodeColors, adjacencyList)) {
                nodeColors[currentNode] = color; // Assign color

                // Recur to assign colors to the next node
                if (tryColoringGraph(currentNode + 1, maxColors, totalNodes, nodeColors, adjacencyList)) {
                    return true;
                }

                // Backtrack: remove the color assignment
                nodeColors[currentNode] = 0;
            }
        }

        // If no color can be assigned to this node, return false
        return false;
    }

    // Main function to check if coloring is possible
    bool graphColoring(vector<vector<int>>& edges, int maxColors, int totalNodes) {
        // Step 1: Create adjacency list for the graph
        vector<int> adjacencyList[totalNodes];

        for (const auto& edge : edges) {
            int u = edge[0];
            int v = edge[1];
            adjacencyList[u].push_back(v);
            adjacencyList[v].push_back(u); // Since the graph is undirected
        }

        // Step 2: Initialize color assignment for each node as 0 (uncolored)
        vector<int> nodeColors(totalNodes, 0);

        // Step 3: Start the coloring process from node 0
        return tryColoringGraph(0, maxColors, totalNodes, nodeColors, adjacencyList);
    }
};

Complexity Analysis:

• Time Complexity:O(M^N) where m is the number of colors and n is the number of nodes, since each node can be colored in m ways and there are n nodes to color.
• Space Complexity:O(N) for the colors array and O(n) for the adjacency list, resulting in O(N) total space complexity.