Posts

4 Applications for DFS and BFS

 1- Count Numbers of Connected Component : __________________________________________________ #include <bits/stdc++.h> using namespace std ; #define endl '\n' #define ll long long const int N = 5e5 + 4 ; vector < int > adjlist [ N ]; bool visited [ N ]; int numo_f_Components = 0 ; int n , m ; void dfs ( int node){ if ( visited [node]== 1 ) return ; visited [node]= true ; for ( auto newnode : adjlist [node]) dfs( newnode ); } int main () { cin >> n >> m ; for ( int i = 0 ; i < m ; i ++){ int x , y ; cin >> x >> y ; adjlist [ x ].push_back( y ); adjlist [ y ].push_back( x ); } for ( int i = 0 ; i < n ; i ++){ if (! visited [ i ]) { numo_f_Components ++; dfs( i ); } } return 0 ; } _____________________________________________________________________________________________________ 2-the vertix belongs to which component (DFS) ____________

Leet code (Reverse Integer)

  7.   Reverse Integer Given a signed 32-bit integer  x , return  x  with its digits reversed . If reversing  x  causes the value to go outside the signed 32-bit integer range  [-2 31 , 2 31  - 1] , then return  0 . Assume the environment does not allow you to store 64-bit integers (signed or unsigned).   Example 1: Input: x = 123 Output: 321 Example 2: Input: x = -123 Output: -321 Example 3: Input: x = 120 Output: 21 Example 4: Input: x = 0 Output: 0   Constraints: -2 31  <= x <= 2 31  - 1 Solution class Solution { public:     int reverse(int x) {         int rev = 0;         while (x) {             int pop = x % 10;             x /= 10;             if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;             if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;             rev = rev * 10 + pop;         }         return rev;   }      };

Graph Theory(Breadth First Search)

Image
Hellllo, guys new article again WOwwwww  in this article I will talk about another search way in  graph topic, which is DFS.    first, let's speak about how it's working?? ok, as you see now in this image Bfs is working by search level by level it searches in the level one  first then when it's complete level one it starts a search in the next level and so on. ( notes that Bfs work in an unweighted graph  or weighted graph with equal-weighted ) ( notes that Bfs is used to search to the shortest path )  EXAMPLE :( maze solver ) now, we wanna ask a question how can i know the level of the node in implementation? we will write this algorithm by using a queue of pair the first one will be the value of the node and the second one will be the level . Like:   vector<int> BFS(int s, vector<vector<int> > & adjList) { vector<int> len(sz(adjList), OO);  //oo is define to infinity queue< pair<int, int> > q; q.push(MP(s, 0)), len[s] = 0; i

Graph Theory(Depth First Search)

Image
Hello, guys in this article I will speak about the important searching way which is used in graph theory.  Depth-first-search, ok first what is it? and how it works? Here we have a photo which describes how this algorithm work:    In this algorithm, we move from the root of the tree to the depth level then we move up again and down again. as you see in the photo;    now one will ask me ok how can I implement that? I will write an Implementation in C++ language void dfs(int node) { visited[node] = true; for(int i=0;i< adj[node];i++) { int child = adj[node][i]; if (!visited[child]) // To avoid cyclic behavior dfs(child); } }    let's talk about Dfs application which is Dfs EdgeClassification . ( notice that it works in Directed graph ) what is it??? let's look first. ok in this photo you will notice four types of edges. the first one is tree Edge : we called that edge is a tree edge when we move from parent to child (like 1  -> 2) the second one is Bac

Graph Theory(adjacency matrix,adjacency list)

Image
today I will speak about one of the most important topics which are graph theory. I will take a long time in this series because I wanna speak a lot of data structure related to graph theory but in the beginning, I will speak about just two representations which are  (adjacency matrix, adjacency list). adjacency matrix the first let's talk about adjacency matrix .this to make a memory representation for any graph (directed or non-directed) we can imagine that Like  code bool adjacency_matrix[100][100];        Example n=3 0 1 0 1 1 0 0 1 1 for(int i=0;i<n;i++) for(int j=0;j<;j++){ int x; cin>>x; adjacency_matrix[i][j]=x; } adjacency list then I will speak about adjacency list, how to represent it in memory and how we implement it with code code vector< vector<int> > adjList1;               if adjacency list without  weight vector< vector< pair<int, int> > > adjList2;    if adjacency list with weight Example-1               3

Cumulative (Prefix) Sum (Part 1)

in this article, we will talk about Cumulative sum but first, let me talk about one of the most  a common problem in computer science if we have an array and we wanna calculate the summation  of a specific range in this array, you will think of nested loops that sound good.  but this solution is (o(n)^2) can we get a better solution ?? Yes, we can do that by using (cumulative sum). ok, what is that exactly? The cumulative sum is a technic we use to get the   summation of a specific range in an array in(o(i)). by generating a new array each element in that array contain the summation of elements before that  element. ok, How we can write this code? ZERO BASED int range(int s,int e,vector<int>&v){ if(s==0)     return v[e];     return v[e]-v[s-1]; } int main() { //zero based     vector<int>v={1,2,3,4,5,6};     vector<int>s(v.size(),0);     for(int i=0;i<v.size();i++){         s[i]+=(i==0)?v[i]:v[i]+s[i-1];     }     cout<<range(2,4,s);     return 0; } ONE BA

Recursion(Part 1)

In this article I will speak about one of the main topics in computer science and I will write some examples to make you know what is that and how you should use it.   Recursion function it’s a function call itself. And this function is consisting of three parts (Base Case, some Logic,  Sub-problem). 1-Base case: this is a case when it happens this recursion function should stop and gave you the result.     2- some Logic: which happens when function called himself. 3- Sub-problem: in this part, the function calls itself by part of it but this calling should never go to infinity. Ex1: void SayHello(int num) {     if(num < 1)                                                                // Base Case                         return;       cout<<"Hello.\n";                  // Some logic       SayHello(num - 1);                // Sub-problem - never go to infinity } Ex2 int Fact(int n) {             if(n <= 1)