Introduction to Graphs

A graph consists of :

• Nodes (Vertices) → entities

• Edges → connections between nodes

Example :

Students in a classroom and their friendships.

1 — 2
|   |
3 — 4

Here :

• Node = Student

• Edge = Friendship

Many real problems can be modeled this way.

---

Directed & Undirected Graphs :

An Undirected Graph is a graph where edges do not have a direction.
If there is an edge between A and B, you can travel both ways.

Example: Friendship network — if A is friends with B, B is also friends with A.

Representation:

A — B

A Directed Graph is a graph where edges have a direction.
If there is an edge A → B, you can go from A to B, but not necessarily from B to A.

Example: Twitter/Instagram follow — if A follows B, B may not follow A.

Representation:

A → B

---

Rumor Spreading Example

Imagine :

• N students in a class

• M friendship relations

Example relations :

1 2
2 3
1 3
2 4
5 6

If student 1 starts a rumor, it spreads to all friends connected to them.

Students 1,2,3,4 will hear the rumor.

But 5 and 6 will not because they are in another group.

---

Graphs are one of the most powerful and widely used data structures in computer science.

Many real-world problems can naturally be represented using graphs. Whenever we have objects connected with relationships, we can model them as a graph.

For example :
Road Maps – Cities connected by roads
Friend Relationships – Connections between individuals

Because graphs are everywhere, learning how to traverse and explore graphs efficiently is extremely important.

Two fundamental algorithms help us explore graphs:

• Depth First Search (DFS)

• Breadth First Search (BFS)

In this blog, we will focus on Depth First Search (DFS).

But before understanding DFS, we must first understand an important concept that powers it:

Recursion

---

Understanding Recursion (The Heart of DFS)

Recursion is a programming technique where a function calls itself to solve smaller parts of a problem.

Instead of solving the entire problem at once, recursion breaks it into smaller subproblems.

Simple Example

Suppose we want to count down from 5 to 1.

void countdown(int n){
    if(n == 0) return;

    cout << n << endl;
    countdown(n - 1);
}

Execution flow :

countdown(5)
  ->countdown(4)
      ->countdown(3)
          ->countdown(2)
              ->countdown(1)
                  ->countdown(0)

Then the recursion stops.

Key Components of Recursion

Every recursive function has two parts :

Base Case

The condition that stops recursion.

if(n == 0) return;

Recursive Call

The function calling itself with a smaller input.

countdown(n-1)

What Happens After the Base Case?

When the base case is hit, the functions do not disappear instantly.

Instead, they start returning one by one in reverse order.
This process is called backtracking.

Think of it like climbing down a staircase and then climbing back up.

Execution return flow :

countdown(0)  → returns to countdown(1)
countdown(1)  → finishes and returns to countdown(2)
countdown(2)  → finishes and returns to countdown(3)
countdown(3)  → finishes and returns to countdown(4)
countdown(4)  → finishes and returns to countdown(5)
countdown(5)  → program ends

Each function waits for the function it called to finish before it can finish itself.

So the order is :

Call phase (going deeper)
5 → 4 → 3 → 2 → 1 → 0

Return phase (backtracking)
0 → 1 → 2 → 3 → 4 → 5

What is Depth First Search ?

DFS is a graph traversal algorithm that:

Explores as far as possible along each branch before backtracking.

Example : Exploring Rooms in a House

Imagine you enter a house with many connected rooms.

You explore the house like this:

1. Enter the first room

2. If there is another room connected, go inside it

3. Keep going deeper from room to room

4. If you reach a room with no new doors, you go back

5. Then you try another door from the previous room

So the process becomes:

• Go forward

• Keep going deeper

• If there is no new room → go back

• Try another path

DFS explores one path completely before moving to another path.

---

DFS Idea

For every node we visit:

1. Mark the node as visited
   This helps us remember that we have already seen this node.

2. Look at its neighbors
   Check all the nodes connected to it.

3. Visit any neighbor that is not visited
   Move to that node.

4. Repeat the same process again
   Keep doing this recursively until all nodes are visited.

---

Representing Graphs

Graphs are commonly stored using Adjacency Lists.

Example graph:

1 -- 2
|    |
3 -- 4

Adjacency List:

1 → 2,3
2 → 1,4
3 → 1,4
4 → 2,3

This allows us to easily find neighbors.

---

DFS Algorithm

Basic idea:

dfs(node):
    mark node as visited

    for each neighbor of node:
        if not visited:
            dfs(neighbor)

---

DFS Implementation (C++)

vector<vector<int>> g;
vector<int> vis;

void dfs(int node)
{
    vis[node] = 1;

    for(auto v : g[node])
    {
        if(!vis[v])
        {
            dfs(v);
        }
    }
}

---

Building the Graph

/*
- resize(n+1, 0) → keeps old values, adds/truncates to size n+1.
- in resize(n+1, 0), any new elements added (beyond the current size) will be initialized to 0.
*/

int n, m;
vector<vector<int>> g;

void solve()
{
    cin >> n >> m;

    g.resize(n+1);

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
        //Undirected graph
    }
}

Here:

• g[node] contains all neighbors of that node.

---

Finding Connected Components

If we run DFS from node 1, it only visits nodes connected to it.

To explore the whole graph:

for each node:
    if not visited:
        run DFS

Example:

int comp = 0;

for(int i=1;i<=n;i++)
{
    if(!vis[i])
    {
        comp++;
        dfs(i);
    }
}

Each DFS call discovers one component.

A graph is the whole network, while a connected component is one connected group inside that network.

Graph:
The entire diagram with all nodes (A–L) and their connections is called a graph.

Connected Components:
Connected components are groups of nodes that are connected to each other but not connected to other groups.

In this diagram:

• Component 1: A, B, C, D, E, F, G, H, I

• Component 2: J, K, L

So, this graph has 2 connected components.

---

Visualization

---

Time Complexity of DFS

For a graph with :

• V vertices

• E edges

DFS complexity :

O(V + E)

Reason :

• Each vertex visited once

• Each edge explored once

This makes DFS extremely efficient even for large graphs.

---

Bipartite Graph

Another powerful application of DFS is checking bipartite graphs.

A graph is bipartite if we can color nodes using two colors such that:

No two adjacent nodes have the same color.

Example:

Red  Bluee  Red
 1-----2-----3
  \         / 
   \       /
    \     /
     Bluee
       4

DFS can assign alternating colors while traversing.

---

Bipartite Check (DFS)

vector<int> color;
bool is_bipartite = true;

void dfs(int node, int col)
{
    color[node] = col;

    for(auto v : g[node])
    {
        if(!vis[v])
        {
            dfs(v, (1+2)-col);
        }
        else if(color[v] == color[node])
        {
            is_bipartite = false;
        }
    }
}
/*
(1 + 2) - col is used to switch between the two colors (1 and 2).
Since : 1 + 2 = 3

the expression becomes : 3 - col

So:
If col = 1 → 3 - 1 = 2
If col = 2 → 3 - 2 = 1

This automatically flips the color when moving to the next node in DFS, ensuring adjacent nodes have different colors in a bipartite graph.
*/

---

Codes

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

int n,m;

vector<vector<int>> g;
vector<int> vis;
vector<int> comp_num;
vector<int> comp_size;

void dfs(int node,int comp_no)
{
    vis[node]=1;
    comp_num[node] = comp_no;
    comp_size[comp_no]++;
    for(auto v:g[node])
    {
        if(!vis[v])
        {
            dfs(v, comp_no);
        }
    }
}

void solve()
{
    cin>>n>>m;

    g.resize(n+1);
    vis.resize(n+1);
    comp_num.resize(n+1);
    comp_size.resize(n+1,0);

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    int comp_no = 0;

    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            comp_no++;
            dfs(i,comp_no);
        }
    }

    int q;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        int a,b;
        cin>>a>>b;
        if(comp_num[a]==comp_num[b])
        {
            cout<<"Yes\n";
        }
        else
        {
            cout<<"No\n";
        }
    }

    for(int i=1;i<=n;i++)
    {
         cout<<comp_size[comp_num[i]]<<endl;
    }

    for(auto v:comp_num)
    {
       cout<<v<<" ";
    }
    cout<<endl;

    for(auto v:comp_size)
    {
       cout<<v<<" ";
    }
    cout<<endl;

    dfs(1);
    for(auto v:vis)
    {
      cout<<v<<" ";
    }
    cout<<endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
}


/*
g[a].push_back(b);
g[b].push_back(a);
This adds both edges (a → b and b → a), making the graph undirected.


If you change it to:
g[a].push_back(b);
and remove the line g[b].push_back(a);, then you're only adding the edge from a to b, making the graph directed.


*****
The Above Code is Doing These
- Number of connected components
- Size of each connected component
- Same component check for queries
*/

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

int n,m;

bool is_bipartite = 1;

vector<vector<int>> g;
vector<int> vis;
vector<int> color;

void dfs(int node,int col)
{
    vis[node]=1;
    color[node]=col;
    for(auto v:g[node])
    {
        if(!vis[v])
        {
            dfs(v,(1+2)-col);
        }
        else if(color[node]==color[v])
        {
            is_bipartite = 0;
        }
    }
}

void solve()
{
    cin>>n>>m;
    g.resize(n+1);
    vis.resize(n+1);
    color.resize(n+1);

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            dfs(i,1);
        }
    }
    if(is_bipartite)
    {
        cout<<"Possible\n";
        for(auto v:color)cout<<v<<" ";cout<<endl;
    }
    else
    {
        cout<<"Not possible\n";
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
}


/*
A graph with only even-length cycles can be bipartite.
A graph with at least one odd-length cycle cannot be bipartite.


Example:
--------
A cycle of length 4 (even) → Bipartite 
A cycle of length 3 (triangle) → Not Bipartite 


*****
The Above Code Just Telling Whether It Is Bipartitite or Not Thats It
If We Want To Know How Many Ways There To Make it Bipartitite Is 2^Number Of Connected Components

Take A Paper And Create This(Non-Directed Graph)
1-2
2-8
8-4
4-1

5-6
6-7

3-9

     1-----2
      \    |
       \   8
        \  |
         \ |
          \|
           4


5-----6
      | 
      |
      7



3------9



Now If We Start From 1(Start With Color1) Then It Is One Possible Answer
If From 1(Start With Color2) Then It Is One Possible Answer

Now If We Start From 5(Start With Color1) Then It Is One Possible Answer
If From 5(Start With Color2) Then It Is One Possible Answer

Now If We Start From 3(Start With Color1) Then It Is One Possible Answer
If From 3(Start With Color2) Then It Is One Possible Answer

So For First Component There Are 2 Possibilities
For Second 2 Possibilities
For Third 2 Possibilities

Total :-
--------
Color1 Color1 Color1
Color1 Color1 Color2
Color1 Color2 Color1
Color2 Color1 Color1
Color2 Color2 Color2
Color2 Color2 Color1
Color2 Color1 Color2
Color1 Color2 Color2
Total 2^3 Possibilities.....
*/