# Graphs 1: DSU, Kruskal Algorithm & Bipartite Graph

---
### Problem 1 Is Knight reachable

Given a N * N chessboard with K Knights placed on it.

If a Knight is reachable from the other Knight, they can swap their positions

Find the number of ways the Knights can rearrange themselves

### Observations

Lets see the positions in which the Knight can move from (i, j).

<img src="https://hackmd.io/_uploads/H17LVIDZR.png" width = 500 />

| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| row | -2 | -2 | -1 | -1 | 1 | 1 | 2 | 2 |
| col | -1 | 1 | -2 | 2 | 2 | -2 | 1 | -1 |

### Example

<img src="https://hackmd.io/_uploads/SkNyHIDWC.png" width = 300 />

### Solution Approach

Lets see what are all the Knights that are reachable.

As we can see that, the Black, Blue, Light Green, Pink, and Purple Knights are reachable, whereas Orange and Dark Green can swap themselves.

<img src="https://hackmd.io/_uploads/S1OgUUvWA.png" width = 500 />

So the answer for the above grid is, **5! x 2!**.

Assume N connected components, then the solution will be

`Ways = (count(CC1)!) * (count(CC2)!)....(count(CCN)!)`

---
### Problem 2 Nearest Hospital

Given a N * M Matrix, the cells of the matrix is either marked as R (Residence) or H (Hospital)

For every residence, find the distance to the nearest Hospital.

From a particular cell, you can move to any adjacent cell (diagonal moves not allowed).

**Example:**

<img src="https://hackmd.io/_uploads/Hk01DID-0.png" width = 300 />

**Answer:**
For the above matrix, lets calculate the distance to the nearest hospital.

The distance matrix (solution) will be

<img src="https://hackmd.io/_uploads/SyhXvLwW0.png" width = 300 />

### Solution Approach

If we start from each Resident and find the Nearest Hospital, is an very unoptimal way, since we traverse the entire graph repeatedly for each resident.

Alternately, what we do here is, we start from the hospital because all the hospitals are similar. If we mark all the source nodes initially and take one-one step outer and mark the distances of those nodes. Here we achieve a very optimal way to solve the problem.

The Algorithm we are going to use here is a BFS but here it is know as **MultiSource BFS**.

Why we call it as MultiSource ?

It simply means, "When we have Multiple Start points" in the graph.

<img src="https://hackmd.io/_uploads/B1BSmuPW0.png" width = 500 />

<img src="https://hackmd.io/_uploads/ryUU7_D-A.png" width = 500 />

---
### Bipartite Graph

Given a graph. Check if it is bipartite?

**Bipartite:** A graph whose can be divided into 2 disjoint and independent sets (u & v) such that every edge of graph connects a node in set u to a node in the set v.

**Example:**

<img src="https://hackmd.io/_uploads/HktlV_PbC.png" width = 500 />

Lets mark the alternate levels with the same set.

<img src="https://hackmd.io/_uploads/HyhUEuw-R.png" width = 500 />

If we carefully see the graph, we can say that, for any node in the set u, it will always have an edge with the set v and vice-versa.

This graph is known as Bipartite.

The moment, if you had an edge between 9-10, the graph is no longer an Bipartite Graph.

<img src="https://hackmd.io/_uploads/SyDMrdw-R.png" width = 500 />

Here the node 9 (from set u) has an edge with the node 10 (with is also from set u).

---
### Graph Coloring

Color the nodes of a graph such that no two adjacent nodes have the same color using minimum number of colors.

**Example:**

<img src="https://hackmd.io/_uploads/HJmXUuv-R.png" width = 300 />

Answer: 2

Minimum number of Colors used is 2.

Before moving forward, Lets see a new concept, Chromatic Number.

### Chromatic Number

Chromatic Number is the Minimum number of colors required to color a graph, such that any pair of adjacent nodes have the same color!

Example:

<img src="https://hackmd.io/_uploads/HJEBwdvWR.png" width = 300 />

> What is the chromatic number of the above graph ?

For Now, Lets start coloring the nodes.

<img src="https://hackmd.io/_uploads/H1XDwuwZC.png" width = 300 />

On the marked node, Can you color with red color ?
or with yellow color ?

No right!

Now lets introduce a new color, blue for that node.

<img src="https://hackmd.io/_uploads/BJDswOPW0.png" width = 300 />

So the chromatic number of the graph is **3**.

Example 2:

<img src="https://hackmd.io/_uploads/HyUZOuDWR.png" width = 300 />

What is the chromatic number of the above graph ?

<img src="https://hackmd.io/_uploads/HJWwdOPZR.png" width = 300 />

For a Fully Connected Graph with N nodes, the Chromatic number is N.

---
### Problem 4 Find Chromatic Number

Given a graph find the chromatic number.

### Solution Approach

There is one possible way to solve this question is Backtracking. The idea is very simple, you will start from a node, assign a color to the current node. Then to all the neighbour, color with a different color.

<img src="https://hackmd.io/_uploads/ryuLZHd-R.png" width = 300 />

### Observation

Lets look into different types of Graphs.

<img src="https://hackmd.io/_uploads/B1nh-r_bA.png" width = 300 />

Think, which graph type is a Bipartite graph?

> Any Graph, which has a Odd Length cycle cannot be a Bipartite Graph.

Is the Given Graph is a Bipartite Graph ?

<img src="https://hackmd.io/_uploads/HJiLfBd-R.png" width = 500 />

> The Graph is Not Bipartite, Since there is a Odd length Cycle.

### Pseudo Code

char color[N + 1] = {'w'};
for(i = 1; i <= N; i++){
    if(color[i] == 'w'){
       if(!isBipartite(i, 'G')){
           return False;
       }
}
}
return True;

bool isBipartite(int Source, char C){
     color[Source] = C;
     char temp;
     if(C == 'B'){
          temp = 'G';
     }
     else{
         temp = 'B';
     }
     for(all u connected to Source){
         if(color[u] == C){
              return False;
         }
         if(color[u] == 'w'){
              if(!isBipartite(u,temp)){
                   return False;
              }
         }
     }
     return True;
}

---
### Problem 5 Maximum Number of Edges in a Bipartite graph

Given a graph which is Bipartite. The Graph is Divided into 2 disjoint and independent sets u and v with N and M nodes respectively. What is the maximum number of edges we can have ?

Example:

Input:
<img src="https://hackmd.io/_uploads/rJ-pQHOZR.png" width = 300 />

### Dry Run

Can we say the any node of the set u, can have form an edge between all the nodes of the set v.

<img src="https://hackmd.io/_uploads/SJar4rubC.png" width = 300 />

If we do the same thing for each node in the set u.

<img src="https://hackmd.io/_uploads/B1ZWBrO-R.png" width = 300 />

The Total Number of Edges formed is **N x M**, which is the maximum possible.

---
### Problem 6 Add edges to maintain bi-partiteness

Given a tree with N nodes find the maximum number of edges that can be added to the tree so that it is still bi-partite graph.

**Example:**

<img src="https://hackmd.io/_uploads/ryWNLB_W0.png" width = 500 />

### Approach

Lets Apply level order traversal here, in which the even levels belongs to a set u and the odd levels nodes belongs to another set v.

<img src="https://hackmd.io/_uploads/ByhWPrd-R.png" width = 500 />

Lets Separate the nodes based on the levels.

<img src="https://hackmd.io/_uploads/r1UVPS_WR.png" width = 300 />

Lets say, we have X nodes on set u, and Y nodes on set v.

Maximum number of Edges = (x * y)

Current number of Edges (Since it is a Tree) = (N-1)

### Extra Edges = [(x * y) - (N - 1)]

---
### Problem 7 Friends Graph

Given a friendship graph of N persons

You can only attend the party if you have minimum K number of friends attending the party.

Find total number of people that can attend the party.

**Example:**

K = 2
Graph:
<img src="https://hackmd.io/_uploads/HyDSYBubR.png" width = 500 />

### Observation

As we can see that the straight forward appraoch will be, Finding the counting the friends of each node and at last count the nodes which has friends >= K.

> But It is Wrong.

Lets see why the previous one is wrong!

### Dry Run

Can Person 1 can attend the party ?

> No, Since they have only one friend.

Can Person 6 can attend the party ?

> No, Since they have only one friend.

Can Person 2 attend the party ?

> If we see the Person 2, he has two friends. But the question here is, "There should be Minimum of K friends **attending** the party". Person 1 cannot attend the party for sure.

<img src="https://hackmd.io/_uploads/r1t4TBuZ0.png" width = 500 />

Rest of the persons have enough friends to attend the part.

<img src="https://hackmd.io/_uploads/HkiYaru-A.png" width = 500 />

### Solution Approach

For a given graph, instead of creating a adjacency graph.

Along with that, lets create a Hashmap to keep track of the neighbour of each node.

<img src="https://hackmd.io/_uploads/HJf9X8OZ0.png" width = 500 />

Insert all the edges in a Min heap, which is used to pop the node with the minimum of edges which has.

If the current node has less than K friends. The for all the neightbours reduce by 1.

<img src="https://hackmd.io/_uploads/rJB2ILdbA.png" width = 500 />