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)

______________________________________________________________________

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N=5e5+4;
vector<int>adjlist[N];
int visited[N];
int numo_f_Components=0;
int n,m;
void dfs(int node){
    if(visited[node]==1)return;
    visited[node]=numo_f_Components;
    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);
       }
   }

    for(int i=0;i<n;i++)cout<<visited[i]<<" ";
    return 0;
}
______________________________________________________________________________________________________

3-the vertix belongs to which component (BFS)

_____________________________________

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N=5e5+4;
vector<int>adjlist[N];
int visited[N];
int numo_f_Components=0;
int n,m;
void dfs(int node){
    if(visited[node]==1)return;
    visited[node]=numo_f_Components;
    for(auto newnode:adjlist[node])
        dfs(newnode);

}

void bfs(int node){

    queue<int>q;
    q.push(node);
    while (!q.empty()){
        node=q.front();
        q.pop();
        if(visited[node])continue;
        visited[node]=numo_f_Components;
        for (auto it: adjlist[node])q.push(it);


    }

}


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++;

           bfs(i);
       }
   }

    for(int i=0;i<n;i++)cout<<visited[i]<<" ";
    return 0;
}
___________________________________________________________________________________________________
4-Find The Path From A To B (DFS)
__________________________________
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N=5e5+4;
vector<int>adjlist[N];
int visited[N];

int n,m;

vector<int>path;
bool done = false;
int target;
void findpathDFS(int node){
    if(visited[node])return;
    visited[node]=1;

    path.push_back(node);

    if(node==target && !done){
        for(auto j:path)cout<<j<<" ";
        cout<<endl;
done=true;
        return;
    }

    for(auto it:adjlist[node])findpathDFS(it);
    path.pop_back();

}

int main() {
   cin>>n>>m>>target;
   for(int i=0;i<m;i++){
       int x,y;
       cin>>x>>y;
       adjlist[x].push_back(y);
       adjlist[y].push_back(x);

   }

   findpathDFS(1);


    return 0;
}
____________________________________________________________________________________________________
5-Find The Path From A To B (BFS)
__________________________________
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N=5e5+4;
vector<int>adjlist[N];
int visited[N];
int n,m;
vector<int>path;

int target;

int parent[N];
void findpathBFS(int node){
    queue<int>q;
    q.push(node);
    visited[node]=1;
    while (!q.empty()){
        node=q.front();
        q.pop();
        for(auto it:adjlist[node]){
            if (!visited[it]){
            parent[it]=node;
            visited[it]=1;
            q.push(it);

            }

        }


    }
    path.push_back(target);
int cur=parent[target];
    while (cur!=0){
        path.push_back(cur);
        cur=parent[cur];

    }
    reverse(path.begin(),path.end());
    for(auto it:path)cout<<it<<' ';
}




int main() {
   cin>>n>>m>>target;
   for(int i=0;i<m;i++){
       int x,y;
       cin>>x>>y;
       adjlist[x].push_back(y);
       adjlist[y].push_back(x);

   }

   findpathBFS(1);


    return 0;
}
__________________________________________________________________________________________________
6- find the smallest lexicographical path(DFS) Can't doing this with BFS
______________________________________________________________________
 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N=5e5+4;
vector<int>adjlist[N];
int visited[N];
int n,m;


vector<int>path;
bool done = false;
int target;
void findpathDFS(int node){
    if(visited[node])return;
    visited[node]=1;

    path.push_back(node);

    if(node==target && !done){
        for(auto j:path)cout<<j<<" ";
        cout<<endl;
done=true;
        return;
    }

    for(auto it:adjlist[node])findpathDFS(it);
    path.pop_back();

}



int main() {
   cin>>n>>m>>target;
   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=1;i<=n;i++)
     sort(adjlist[i].begin(),adjlist[i].end());

   findpathDFS(1);



    return 0;
}

______________________________________________________________________________________________________




Comments

Post a Comment

Popular posts from this blog

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;           ...
Read more

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> ...
Read more

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)                                                     ...
Read more