Day 40 | 2 - Coloring of Graph | C++

Have you heard of a situation where we have to assign a color to nodes of a graph (or its story equivalent) and no two neighbors should have the same color and you have to do so with the minimum number of colors?

This is a famous problem called the NP-hard problem, to calculate all the solutions (which take non-polynomial time which is the reason for the word NP) and then get the count of minimum colors.

But many times, there are situations where reducing some constraints will make it solvable like checking if we can assign only two colors to everyone. 2-SAT is another example of a situation where an NP-Hard (or complete) problem is reduced to a simpler solvable problem by limiting constraints.

Let's focus on Bipartite Graph problems a little.

Today we are going to learn about 2 Coloring of a Graph, also known as Bipartition of a graph.

It has many uses such

1. Checking if we can divide teams in such a way that no two people are close friends in a team.

2. Checking if there is a cycle of odd length in a graph.

3. You will find more when you solve problems, LOL [I meant, etc]

So Basically what you want to do is -

Divide the Graph into two groups such that no two nodes in a group share an edge

How can you do that?

It's actually quite simple - You run a DFS, assign node color and try to assign all adjacent nodes different colors. If you cannot do that, then it's not possible to do so.

/*
Default value / Unassigned value = -1
Colors - 0/1
And 0^1 = 1 and 1^1 = 0
Thus color ^ 1 flips it
*/
bool dfs(int u, int color_assign){
    color[u] = color_assign;
    for(int v: graph[u]){
        if(color[v] == -1){
            if(!dfs(v, color_assign ^ 1))
                return false;
        }
        if(color[v] != color_assign ^ 1)
            return false;
    }
    return true;
}

This is will assign colors to two groups of a connected graph. See the example below -

Yeah, this is it. Seems scary, but is one of the simplest algorithms to implement. The tough part is to know that bipartite will get the answer.

Again we need to practice

Building Teams

Solution

It is a straightforward bipartite problem for practice, just code it out.

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int color[N];
vector<int> g[N];

bool dfs(int u, int color_assign){
    color[u] = color_assign;
    for(int v: g[u]){
        if(color[v] == -1){
            if(!dfs(v, color_assign ^ 1))
                return false;
        }
        if(color[v] != color_assign ^ 1)
            return false;
    }
    return true;
}

int main(){
    int m,n;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    memset(color, -1, sizeof(color));
    for(int i = 1; i <= n; i++){
        if(color[i] != -1)
            continue;
        if(!dfs(i,0)){
            return cout << "IMPOSSIBLE\n",0;
        }
    }
    for(int i = 1; i <= n; i++)
        cout << color[i] + 1 << " ";
}

BUGLIFE

Input:
2
3 3
1 2
2 3
1 3
4 2
1 2
3 4

Output:
Scenario #1:
Suspicious bugs found!
Scenario #2:
No suspicious bugs found!

Graph Without Long Directed Paths

Example

Input
6 5
1 5
2 1
1 4
3 1
6 1
Output
YES
10100

You know it is something related to the bipartite graph, try it on your own that way it will be even more fun to read the solution.

Go try it...

Okay, I hope you just didn't continue to read without trying but I have faith in you that did try it. So, let's discuss the solution.

Assume we have this graph

If we 2-color it, we will get this

If we add an edge from one type of color to another, like green to blue or opposite, then from one node you can go outward and another come inwards and not again outwards, limiting your path to length 1. Something like

You can code it like this -

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int color[N];
vector<int> g[N];

bool dfs(int u, int color_assign){
    color[u] = color_assign;
    for(int v: g[u]){
        if(color[v] == -1){
            if(!dfs(v, color_assign ^ 1))
                return false;
        }
        if(color[v] != color_assign ^ 1)
            return false;
    }
    return true;
}

int main(){
    int m,n;
    cin >> n >> m;
    vector<pair<int,int>> edges;
    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
        edges.emplace_back(a,b);
    }
    memset(color, -1, sizeof(color));
    for(int i = 1; i <= n; i++){
        if(color[i] != -1)
            continue;
        if(!dfs(i,0)){
            return cout << "NO\n",0;
        }
    }
    cout << "YES\n";
    for(int i = 0; i < m; i++){
        cout << color[edges[i].first];
    }
}

Please like and share my posts if they are helpful.