Denisse's Newsletter
Posts
Get better not bitter 🔥

Get better not bitter 🔥

Day 2 of Mastering Graphs

Denisse Damian
August 29, 2024

In partnership with

TLDR

Welcome!
The best broth on the planet, Read unbiased news
Interacting with our sponsors helps keep the newsletter free ❤️
Recommendations I live by!
Self-Gaslight of the week - Master your behavioral interview
JOBS & SCHOLARSHIPS

Hello and welcome back brave human being!

Early in my career, I thought I didn’t pass an interview because the interviewer didn’t like me. So I chit-chatted during interviews and tried to be as likable as possible.

Until one day, an interviewer told me.

“ I suggest you focus on the problem instead of talking.”

I thought it was because she didn’t like me, since I got rejected.

But as I get older, I realize that being likable only gets you so far.

You need to master the technical skills as well.

And that is why you are here!!!!!! So LFG!

LeetCode problem

Day 2 :

You have a graph of `n` nodes. You are given an integer `n` and an array `edges` where `edges[i] = [ai, bi]` indicates that there is an edge between `ai` and `bi` in the graph.

Return *the number of connected components in the graph*.

Before we dive in,

Breathe.

Let’s analyze the problem a bit, and note, how the problem says:

there is an edge between `ai` and `bi` in the graph.

This indicates that the graph is bidirectional, meaning if the node ai is connected to node bi then bi is also connected to ai In our adjacency matrix, we represent this relationship by including ai as a neighbor of bi and bi as a neighbor of ai.

Let's start by constructing the adjacency matrix , which is just how we represent a relationship.

Now let’s build it:

for(auto x: edges){
   adj[ x[0] ].push_back( x[1] );
   adj[ x[1] ].push_back( x[0] );
  }

Once we’ve built our adjacency matrix, the magic happens. 🪄

We’ll iterate through the matrix, and for each node that hasn’t been visited, we’ll explore it along with all of its connected neighbors.

for(int x=0; x<adj.size();x++){ 
    if(!visited[x]){ 
        DFS(x, adj, visited); 
         connected++;
    }

We'll pass the node to our DFS function, which will ensure that all of its neighbors are explored.

Once all neighbors of a node are explored, it means we've fully traversed all nodes within that connected component or island.

After finishing the recursive exploration for one component, we'll increment our component counter, then move on to explore the remaining unvisited nodes.

Complete code:

 
int connected=0; 
void DFS(int source,vector<vector<int>>& adj, vector<bool>& visited){
        visited[source] = true; 
        for(int x = 0; x< adj[source].size(); x++){
            if(!visited[adj[source][x]]){
                DFS(adj[source][x],adj,visited); 
            }
           
        }
    }

    
int countComponents(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n); 
    vector<bool> visited(n, false);
       for(auto e :edges){
        adj[e[0]].push_back(e[1]);
         adj[e[1]].push_back(e[0]);
       }
       for(int x=0; x<adj.size();x++){
            if(!visited[x]){
                DFS(x, adj, visited);
                connected++;
            }
       }
       return connected; 
        
    }

What would be the O Notation?

Where V represents Vertices and E represents the relationships

Help me maintain this newsletter free, and interact with our sponsors! 🙂

All your news. None of the bias.

Be the smartest person in the room by reading 1440! Dive into 1440, where 3.5 million readers find their daily, fact-based news fix. We navigate through 100+ sources to deliver a comprehensive roundup from every corner of the internet – politics, global events, business, and culture, all in a quick, 5-minute newsletter. It's completely free and devoid of bias or political influence, ensuring you get the facts straight.

Subscribe to 1440 today.