-
Notifications
You must be signed in to change notification settings - Fork 77
/
M – Coloring_Problem.cpp
92 lines (73 loc) · 1.85 KB
/
M – Coloring_Problem.cpp
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
81
82
83
84
85
86
87
88
89
90
91
92
// Problem Statement: Given an undirected graph and a number m, determine if the graph can be colored with at most m colors such that no two adjacent vertices of the graph are colored with the same color.
// Examples:
// Example 1:
// Input:
// N = 4
// M = 3
// E = 5
// Edges[] = {
// (0, 1),
// (1, 2),
// (2, 3),
// (3, 0),
// (0, 2)
// }
// Output: 1
// Explanation: It is possible to colour the given graph using 3 colours.
// Example 2:
// Input:
// N = 3
// M = 2
// E = 3
// Edges[] = {
// (0, 1),
// (1, 2),
// (0, 2)
// }
// Output: 0
// Explanation: It is not possible to color.
#include<bits/stdc++.h>
using namespace std;
bool isSafe(int node, int color[], bool graph[101][101], int n, int col) {
for (int k = 0; k < n; k++) {
if (k != node && graph[k][node] == 1 && color[k] == col) {
return false;
}
}
return true;
}
bool solve(int node, int color[], int m, int N, bool graph[101][101]) {
if (node == N) {
return true;
}
for (int i = 1; i <= m; i++) {
if (isSafe(node, color, graph, N, i)) {
color[node] = i;
if (solve(node + 1, color, m, N, graph)) return true;
color[node] = 0;
}
}
return false;
}
//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 graphColoring(bool graph[101][101], int m, int N) {
int color[N] = {
0
};
if (solve(0, color, m, N, graph)) return true;
return false;
}
int main() {
int N = 4;
int m = 3;
bool graph[101][101];
memset(graph, false, sizeof graph);
// Edges are (0, 1), (1, 2), (2, 3), (3, 0), (0, 2)
graph[0][1] = 1; graph[1][0] = 1;
graph[1][2] = 1; graph[2][1] = 1;
graph[2][3] = 1; graph[3][2] = 1;
graph[3][0] = 1; graph[0][3] = 1;
graph[0][2] = 1; graph[2][0] = 1;
cout << graphColoring(graph, m, N);
}