GeeksforGeeks : M Coloring Problem

05110

Problem

https://www.geeksforgeeks.org/problems/m-coloring-problem-1587115620/1

You are given an undirected graph consisting of v vertices and a list of edges, along with an integer m. Your task is to determine whether it is possible to color the graph using at most m different colors such that no two adjacent vertices share the same color. Return true if the graph can be colored with at most m colors, otherwise return false.

Note: The graph is indexed with 0-based indexing.

Examples

Input: v = 4, edges[] = [(0,1),(1,2),(2,3),(3,0),(0,2)], m = 3
Output: true
Explanation: It is possible to color the given graph using 3 colors, for example, one of the possible ways vertices can be colored as follows:
Vertex 0: Color 3
Vertex 1: Color 2
Vertex 2: Color 1
Vertex 3: Color 2

Input: v = 3, edges[] = [(0,1),(1,2),(0,2)], m = 2
Output: false
Explanation: It is not possible to color the given graph using only 2 colors because vertices 0, 1, and 2 form a triangle.
Expected Time Complexity: O(mV)
Expected Auxiliary Space: O(v2)

Constraints

1 ≤ v ≤ 20
1 ≤ edges.size() ≤ (v*(v-1))/2
0 ≤ edges[i][j] ≤ n-1
1 ≤ m ≤ v

Intuition

For each of the nodes, we need to put the colors such that, if we look at the neighbours of every node, they should not be equal. This means, once we apply a color, say colorA, to the 0th node, all the children or neighbours of the 0th node shouldn’t be colorA.
This must hold true for all the nodes, and we can try all possibilities of color combinations and see if any of the combinations are suitable for our scenario.
Thus, we can recursively try every combination, and if one combination holds, then we return true. If none of the combination holds, then return false.

Approach

  • Build the graph using an adjacency list representation.
  • Start coloring from the first node, say the 0th node.
  • Try all the m combinations of color on the 0th node, where we will be checking if any of the neighbours have having same color. If not, then we will color the 0th node with say colorA and move to the next node, ie 1st node.
  • This is repeated until the last node.

Time and Space Complexity

O(V + E) for building graph
O(E) for the isPossibleToColorThisNode method checks whether a neighbour has the same color.
O(M^V) for trying all combinations for each vertex.

So total time complexity: O(M^V).

Space Complexity : O(V) + O(recursion stack spaces)

Code 

<span>class</span> <span>Solution</span> <span>{</span>
    <span>boolean</span> <span>graphColoring</span><span>(</span><span>int</span> <span>v</span><span>,</span> <span>List</span><span><</span><span>int</span><span>[]></span> <span>edges</span><span>,</span> <span>int</span> <span>m</span><span>)</span> <span>{</span>
        <span>// code here</span>
        <span>if</span> <span>(</span><span>edges</span> <span>==</span> <span>null</span> <span>||</span> <span>edges</span><span>.</span><span>size</span><span>()</span> <span>==</span> <span>0</span><span>)</span> <span>{</span>
            <span>return</span> <span>false</span><span>;</span>
        <span>}</span>
        <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>graph</span> <span>=</span> <span>buildGraph</span><span>(</span><span>edges</span><span>,</span> <span>v</span><span>);</span>
        <span>int</span> <span>[]</span> <span>colorTrack</span> <span>=</span> <span>new</span> <span>int</span><span>[</span><span>v</span><span>];</span>
        <span>return</span> <span>isPossibleToColor</span><span>(</span><span>graph</span><span>,</span> <span>0</span><span>,</span> <span>colorTrack</span><span>,</span> <span>v</span><span>,</span> <span>m</span><span>);</span>
    <span>}</span>
    <span>private</span> <span>boolean</span> <span>isPossibleToColor</span><span>(</span><span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>graph</span><span>,</span> <span>int</span> <span>node</span><span>,</span> <span>int</span> <span>[]</span> <span>colorTrack</span><span>,</span> <span>int</span> <span>totalNodes</span><span>,</span> <span>int</span> <span>totalColor</span><span>)</span> <span>{</span>
        <span>if</span> <span>(</span><span>totalNodes</span> <span>==</span> <span>node</span><span>)</span> <span>{</span>
            <span>return</span> <span>true</span><span>;</span>
        <span>}</span>
        <span>for</span> <span>(</span><span>int</span> <span>col</span> <span>=</span> <span>1</span><span>;</span> <span>col</span> <span><=</span> <span>totalColor</span><span>;</span> <span>col</span><span>++)</span> <span>{</span>
            <span>if</span> <span>(</span><span>isPossibleToColorThisNode</span><span>(</span><span>col</span><span>,</span> <span>graph</span><span>,</span> <span>node</span><span>,</span> <span>colorTrack</span><span>))</span> <span>{</span>
                <span>colorTrack</span><span>[</span><span>node</span><span>]</span> <span>=</span> <span>col</span><span>;</span>
                <span>if</span> <span>(</span><span>isPossibleToColor</span><span>(</span><span>graph</span><span>,</span> <span>node</span> <span>+</span> <span>1</span><span>,</span> <span>colorTrack</span><span>,</span> <span>totalNodes</span><span>,</span> <span>totalColor</span><span>))</span> <span>{</span>
                    <span>return</span> <span>true</span><span>;</span>
                <span>}</span>
                <span>colorTrack</span><span>[</span><span>node</span><span>]</span> <span>=</span> <span>0</span><span>;</span>
            <span>}</span>
        <span>}</span>
        <span>return</span> <span>false</span><span>;</span>
    <span>}</span>
    <span>private</span> <span>boolean</span> <span>isPossibleToColorThisNode</span><span>(</span><span>int</span> <span>color</span><span>,</span> <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>graph</span><span>,</span> <span>int</span> <span>node</span><span>,</span> <span>int</span> <span>[]</span> <span>colorTrack</span><span>)</span> <span>{</span>
        <span>List</span><span><</span><span>Integer</span><span>></span> <span>children</span> <span>=</span> <span>graph</span><span>.</span><span>get</span><span>(</span><span>node</span><span>);</span>
        <span>for</span> <span>(</span><span>Integer</span> <span>child</span> <span>:</span> <span>children</span><span>)</span> <span>{</span>
            <span>if</span> <span>(</span><span>colorTrack</span><span>[</span><span>child</span><span>]</span> <span>==</span> <span>color</span><span>)</span> <span>{</span>
                <span>return</span> <span>false</span><span>;</span>
            <span>}</span>
        <span>}</span>
        <span>return</span> <span>true</span><span>;</span>
    <span>}</span>
    <span>private</span> <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>buildGraph</span><span>(</span><span>List</span><span><</span><span>int</span><span>[]></span> <span>edges</span><span>,</span> <span>int</span> <span>n</span><span>)</span> <span>{</span>
        <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>graph</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
        <span>for</span> <span>(</span><span>int</span> <span>node</span> <span>=</span> <span>0</span><span>;</span> <span>node</span> <span><</span> <span>n</span><span>;</span> <span>node</span><span>++)</span> <span>{</span>
            <span>graph</span><span>.</span><span>add</span><span>(</span><span>new</span> <span>ArrayList</span><span><>());</span>
        <span>}</span>
        <span>for</span> <span>(</span><span>int</span> <span>[]</span> <span>edge</span> <span>:</span> <span>edges</span><span>)</span> <span>{</span>
            <span>graph</span><span>.</span><span>get</span><span>(</span><span>edge</span><span>[</span><span>0</span><span>]).</span><span>add</span><span>(</span><span>edge</span><span>[</span><span>1</span><span>]);</span>
            <span>graph</span><span>.</span><span>get</span><span>(</span><span>edge</span><span>[</span><span>1</span><span>]).</span><span>add</span><span>(</span><span>edge</span><span>[</span><span>0</span><span>]);</span>
        <span>}</span>
        <span>return</span> <span>graph</span><span>;</span>
    <span>}</span>
<span>}</span>
<span>class</span> <span>Solution</span> <span>{</span>
    <span>boolean</span> <span>graphColoring</span><span>(</span><span>int</span> <span>v</span><span>,</span> <span>List</span><span><</span><span>int</span><span>[]></span> <span>edges</span><span>,</span> <span>int</span> <span>m</span><span>)</span> <span>{</span>
        <span>// code here</span>
        <span>if</span> <span>(</span><span>edges</span> <span>==</span> <span>null</span> <span>||</span> <span>edges</span><span>.</span><span>size</span><span>()</span> <span>==</span> <span>0</span><span>)</span> <span>{</span>
            <span>return</span> <span>false</span><span>;</span>
        <span>}</span>
        <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>graph</span> <span>=</span> <span>buildGraph</span><span>(</span><span>edges</span><span>,</span> <span>v</span><span>);</span>
        <span>int</span> <span>[]</span> <span>colorTrack</span> <span>=</span> <span>new</span> <span>int</span><span>[</span><span>v</span><span>];</span>
        <span>return</span> <span>isPossibleToColor</span><span>(</span><span>graph</span><span>,</span> <span>0</span><span>,</span> <span>colorTrack</span><span>,</span> <span>v</span><span>,</span> <span>m</span><span>);</span>
    <span>}</span>

    <span>private</span> <span>boolean</span> <span>isPossibleToColor</span><span>(</span><span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>graph</span><span>,</span> <span>int</span> <span>node</span><span>,</span> <span>int</span> <span>[]</span> <span>colorTrack</span><span>,</span> <span>int</span> <span>totalNodes</span><span>,</span> <span>int</span> <span>totalColor</span><span>)</span> <span>{</span>
        <span>if</span> <span>(</span><span>totalNodes</span> <span>==</span> <span>node</span><span>)</span> <span>{</span>
            <span>return</span> <span>true</span><span>;</span>
        <span>}</span>
        <span>for</span> <span>(</span><span>int</span> <span>col</span> <span>=</span> <span>1</span><span>;</span> <span>col</span> <span><=</span> <span>totalColor</span><span>;</span> <span>col</span><span>++)</span> <span>{</span>
            <span>if</span> <span>(</span><span>isPossibleToColorThisNode</span><span>(</span><span>col</span><span>,</span> <span>graph</span><span>,</span> <span>node</span><span>,</span> <span>colorTrack</span><span>))</span> <span>{</span>
                <span>colorTrack</span><span>[</span><span>node</span><span>]</span> <span>=</span> <span>col</span><span>;</span>
                <span>if</span> <span>(</span><span>isPossibleToColor</span><span>(</span><span>graph</span><span>,</span> <span>node</span> <span>+</span> <span>1</span><span>,</span> <span>colorTrack</span><span>,</span> <span>totalNodes</span><span>,</span> <span>totalColor</span><span>))</span> <span>{</span>
                    <span>return</span> <span>true</span><span>;</span>
                <span>}</span>
                <span>colorTrack</span><span>[</span><span>node</span><span>]</span> <span>=</span> <span>0</span><span>;</span>
            <span>}</span>
        <span>}</span>
        <span>return</span> <span>false</span><span>;</span>
    <span>}</span>

    <span>private</span> <span>boolean</span> <span>isPossibleToColorThisNode</span><span>(</span><span>int</span> <span>color</span><span>,</span> <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>graph</span><span>,</span> <span>int</span> <span>node</span><span>,</span> <span>int</span> <span>[]</span> <span>colorTrack</span><span>)</span> <span>{</span>
        <span>List</span><span><</span><span>Integer</span><span>></span> <span>children</span> <span>=</span> <span>graph</span><span>.</span><span>get</span><span>(</span><span>node</span><span>);</span>
        <span>for</span> <span>(</span><span>Integer</span> <span>child</span> <span>:</span> <span>children</span><span>)</span> <span>{</span>
            <span>if</span> <span>(</span><span>colorTrack</span><span>[</span><span>child</span><span>]</span> <span>==</span> <span>color</span><span>)</span> <span>{</span>
                <span>return</span> <span>false</span><span>;</span>
            <span>}</span>
        <span>}</span>
        <span>return</span> <span>true</span><span>;</span>
    <span>}</span>

    <span>private</span> <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>buildGraph</span><span>(</span><span>List</span><span><</span><span>int</span><span>[]></span> <span>edges</span><span>,</span> <span>int</span> <span>n</span><span>)</span> <span>{</span>
        <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>graph</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
        <span>for</span> <span>(</span><span>int</span> <span>node</span> <span>=</span> <span>0</span><span>;</span> <span>node</span> <span><</span> <span>n</span><span>;</span> <span>node</span><span>++)</span> <span>{</span>
            <span>graph</span><span>.</span><span>add</span><span>(</span><span>new</span> <span>ArrayList</span><span><>());</span>
        <span>}</span>
        <span>for</span> <span>(</span><span>int</span> <span>[]</span> <span>edge</span> <span>:</span> <span>edges</span><span>)</span> <span>{</span>
            <span>graph</span><span>.</span><span>get</span><span>(</span><span>edge</span><span>[</span><span>0</span><span>]).</span><span>add</span><span>(</span><span>edge</span><span>[</span><span>1</span><span>]);</span>
            <span>graph</span><span>.</span><span>get</span><span>(</span><span>edge</span><span>[</span><span>1</span><span>]).</span><span>add</span><span>(</span><span>edge</span><span>[</span><span>0</span><span>]);</span>
        <span>}</span>
        <span>return</span> <span>graph</span><span>;</span>
    <span>}</span>
<span>}</span>
class Solution {
    boolean graphColoring(int v, List<int[]> edges, int m) {
        // code here
        if (edges == null || edges.size() == 0) {
            return false;
        }
        List<List<Integer>> graph = buildGraph(edges, v);
        int [] colorTrack = new int[v];
        return isPossibleToColor(graph, 0, colorTrack, v, m);
    }

    private boolean isPossibleToColor(List<List<Integer>> graph, int node, int [] colorTrack, int totalNodes, int totalColor) {
        if (totalNodes == node) {
            return true;
        }
        for (int col = 1; col <= totalColor; col++) {
            if (isPossibleToColorThisNode(col, graph, node, colorTrack)) {
                colorTrack[node] = col;
                if (isPossibleToColor(graph, node + 1, colorTrack, totalNodes, totalColor)) {
                    return true;
                }
                colorTrack[node] = 0;
            }
        }
        return false;
    }

    private boolean isPossibleToColorThisNode(int color, List<List<Integer>> graph, int node, int [] colorTrack) {
        List<Integer> children = graph.get(node);
        for (Integer child : children) {
            if (colorTrack[child] == color) {
                return false;
            }
        }
        return true;
    }

    private List<List<Integer>> buildGraph(List<int[]> edges, int n) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int node = 0; node < n; node++) {
            graph.add(new ArrayList<>());
        }
        for (int [] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        return graph;
    }
}

Enter fullscreen mode Exit fullscreen mode

原文链接：GeeksforGeeks : M Coloring Problem

展开阅读全文
© 版权声明
文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END
Java（EN）
# java# programming# learning# algorithms
喜欢就支持一下吧
点赞10 分享
Your dream is like a flower. if you water it patiently, the flower will come out beautifully.
即使是最简单的梦想，用心浇灌，也能开出绚烂的花
评论 抢沙发

请登录后发表评论

    暂无评论内容

文章目录
kity的头像-拾光赋
文章目录
今日剩余 58.7%
本周剩余 79.8%
本月剩余 28.6%
本年剩余 69.5%
最近评论
杀人蜂的头像-拾光赋

杀人蜂8天前0

我很好奇这个网站能提供什么
Vito的头像-拾光赋

Vito6个月前2

你就是我心中的那首忐忑，总是让我惊心动魄
Jason.Meng的头像-拾光赋钻石会员

Jason.Meng徽章-人气大使-拾光赋6个月前2

总是会在人生的不同阶段反复爱上大佬的文章~
每日一言
Your dream is like a flower. if you water it patiently, the flower will come out beautifully.
即使是最简单的梦想，用心浇灌，也能开出绚烂的花