Group non-connected vertices

96 views Asked by At

I want to group non-connected vertices in a graph and minimize the number of these groups. In another word, given a collection of vertices, divide them into minimum number of groups but at the same time no two connected vertices in the same group

Example

here

Answer should be 3 groups: the first: 0, 3 the second: 1 the third: 2

I tried to solve it using brute force by storing the graph into adjacency matrix but it's not working.

for (int i = 0; i < n; i++) {
    if (!vis[i]) {
        for (int j = 0; j < n; j++) {
            if (!adjMat[i][j] && !vis[j]) {
                vis[j] = true;
            }
        }
        vis[i] = true;
        groups++;
    }
}
0

There are 0 answers