DSA-Problem-Solutions/Backtracking_Graph_Coloring.cpp at main · kevin-t11/DSA-Problem-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//{ Driver Code Starts
#include <bits/stdc++.h>
using namespace std;


// } Driver Code Ends
class Solution{
public:
    // Function to determine if graph can be coloured with at most M colours such
    // that no two adjacent vertices of graph are coloured with same colour.

    bool isSafe(int node, int color[], bool graph[101][101], int n, int clr)
    {
        for(int nbr = 0; nbr<n; nbr++)
        {
            if(nbr != node && graph[nbr][node] == 1 && color[nbr] == clr)  // graph[nbr][node] == 1 means there is an edge
                return false;
        }
        return true;
    }

    bool solve(int node, bool graph[101][101], int color[], int m, int n)
    {
        //reached to the last node
        if(node == n)
            return true;

        for(int clr = 1; clr <= m; clr++)
        {
            if(isSafe(node, color, graph, n, clr))
            {
                //consider the color of particular node
                color[node] = clr;

                if(solve(node+1, graph, color, m, n))
                    return true;

                //backtracking
                color[node] = 0;
            }
        }
        return false;
    }

    bool graphColoring(bool graph[101][101], int m, int n) {

        int color[n] = {0};
        int strtnode = 0;
        if(solve(strtnode, graph, color, m, n) == true)
            return true;
        return false;
    }
};

//{ Driver Code Starts.

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m, e;
        cin >> n >> m >> e;
        int i;
        bool graph[101][101];
        for (i = 0; i < n; i++) {
            memset(graph[i], 0, sizeof(graph[i]));
        }
        for (i = 0; i < e; i++) {
            int a, b;
            cin >> a >> b;
            graph[a - 1][b - 1] = 1;
            graph[b - 1][a - 1] = 1;
        }
        Solution ob;
        cout << ob.graphColoring(graph, m, n) << endl;
    }
    return 0;
}

// } Driver Code Ends