DFS (Depth-First Search) Algorithm Code in C/C++

Depth-First Search (DFS) is a graph traversal algorithm that explores vertices or nodes of a graph in depth before visiting the neighboring vertices. It starts at a given vertex and systematically explores as far as possible along each branch before backtracking.

The DFS algorithm follows these steps:

1. Start by selecting a source vertex to begin the traversal.

2. Mark the source vertex as visited and process it. This may involve performing a specific action on the vertex, such as printing its value.

3. Explore an unvisited neighbor of the current vertex. If there are multiple unvisited neighbors, select one of them arbitrarily.

4. Repeat step 3 recursively for the chosen neighbor. Mark it as visited and process it.

5. If there are no unvisited neighbors, backtrack to the previous vertex (i.e., return from the recursive call).

6. Repeat steps 3-5 until all vertices have been visited.

DFS can be implemented using recursion or a stack data structure. The recursive implementation uses the call stack implicitly to keep track of the visited vertices and backtracks when necessary. The iterative implementation, using a stack, simulates the call stack explicitly.

DFS is useful for various graph-related problems, such as finding connected components, detecting cycles, performing topological sorting, and solving maze problems.

It's important to note that DFS doesn't guarantee the shortest path between two vertices. It may traverse long paths before exploring shorter ones. If a complete traversal of all vertices is required, DFS can ensure that every vertex is visited exactly once.

However, in the case of a disconnected graph, it's necessary to apply DFS to each unvisited vertex to cover all components.

Overall, DFS is a fundamental graph traversal algorithm that provides a way to explore and analyze graphs in a systematic manner.

#include <stdio.h> #define MAX_NODES 100 int visited[MAX_NODES]; int adjacencyMatrix[MAX_NODES][MAX_NODES]; int numNodes; void initialize() { int i, j; for (i = 0; i < MAX_NODES; i++) { visited[i] = 0; for (j = 0; j < MAX_NODES; j++) { adjacencyMatrix[i][j] = 0; } } } void addEdge(int startNode, int endNode) { adjacencyMatrix[startNode][endNode] = 1; adjacencyMatrix[endNode][startNode] = 1; } void depthFirstSearch(int currentNode) { int i; printf("%d ", currentNode); visited[currentNode] = 1; for (i = 0; i < numNodes; i++) { if (adjacencyMatrix[currentNode][i] == 1 && visited[i] == 0) { depthFirstSearch(i); } } } int main() { int i, j; int startNode; printf("Enter the number of nodes: "); scanf("%d", &numNodes); initialize(); printf("Enter the adjacency matrix:\n"); for (i = 0; i < numNodes; i++) { for (j = 0; j < numNodes; j++) { scanf("%d", &adjacencyMatrix[i][j]); } } printf("Enter the starting node: "); scanf("%d", &startNode); printf("DFS traversal starting from node %d: ", startNode); depthFirstSearch(startNode); return 0; }

By Md. Rahat (CSE, BU)

Codeforces Solution 71A Way Too Long Words || Codeforces Solution 71A in C language

In this section , I am gonna give you the source code of the codeforces solution of the problem 71A  Way Too Long Words.
Problem Name: Way Too Long Words
Online Judge: Codeforces.com
The below given code is written in C language. :

1. #include<stdio.h>
2. #include<ctype.h>
3. int main(){
4. int n,i,m;
5. char x[6000];
6. scanf("%d",&n);
7. for(i=1;i<=n;i++){
8. scanf("%s",&x);
9. int l=strlen(x);
10.  
11. if(l>10){
12.  
13. printf("%c",x[0]);
14. printf("%d",l-2);
15. printf("%c\n",x[l-1]);
16.  
17. }
18. else printf("%s\n",x);}
19. return 0;
20. }

In python (basically Python 3) Language , the solution should be :

1. i=input
2. for _ in [0]*int(i()):
3. s=i();l=len(s)-2;print([s,s[0]+str(l)+s[-1]][l>8])

Codeforces Problems Solution 226A - Stones on the Table

Hi friends, I am going to post the solve of the problem '226A - Stones on the Table' of Codeforces.
The problem screenshots is given below:

Code:
/// OmShantihari /// Author: Sujan Mridha /// CSE, University of Barishal #include <iostream> using namespace std; int main () { int n,s=0; string m; cin>>n>>m; if (n==1) { cout<<"0"<<endl; return 0; } for (int i=0;i<n-1;i++) { if (m[i]==m[i+1]) s++; } cout<<s<<endl; return 0; }

Codeforces Problems' Solution (339A - Helpful Maths)

The solution of the problem is given below:


#include <stdio.h>
#include <string.h>
int main ()
{
      char s[1000];
      int i, j = 0, k, l, ln, arr[1000], m, n, temp;
      scanf("%s", s);
      ln = strlen(s);
      for(i = 0; i < ln; i++)
      {
          if((i % 2) == 0)
          {
              arr[j] = (int) s[i];
              j++;
          }
      }
      for(m = 1; m < j; m++)
     {
          for(n = 0; n < (j - m); n++)
         {
              if(arr[n] > arr[n + 1])
              {
                  temp = arr[n];
                  arr[n] = arr[n + 1];
                  arr[n + 1] = temp;
              }
          }
      }
      for(k = 0; k < j; k++)
      {
          if(k == (j - 1))
          {
              printf("%c", (char) arr[k]);
          }
          else
          {
              printf("%c%c", (char) arr[k], '+');
          }
      }
      printf("\n");

      return 0;
}

Codeforces Solution of 112A - Petya and Strings in C

Hi friends, I am going to post the solve of the problem '112A - Petya and Strings' of Codeforces.
The problem screenshot is given below:

Code:
/// OmShantihari /// Author: Sujan Mridha /// CSE, University of Barishal#include<stdio.h> #include<string.h> int main() { int x, i,o,l; x=0; char a[200],b[200]; scanf("%s %s",&a,&b); l=strlen(a); for (i=0;i<l;i++) { o=a[i]-b[i]; if (o!=0 && o!=32 && o!=-32) { if (a[i]<='z' && b[i]<='z' && a[i]>='a' && b[i]>='a') { if (a[i]>b[i]) { x=1; break; } else { x=-1; break; } } if (a[i]<='Z' && b[i]<='Z' && a[i]>='A' && b[i]>='A') { if (a[i]>b[i]) { x=1; break; } else { x=-1; break; } } if (a[i]<='Z' && a[i]>='A' && b[i]<='z' && b[i]>='a') { if (a[i]+32>b[i]) { x=1; break; } else { x=-1; break; } } if (a[i]<='z' && a[i]>='a' && b[i]<='Z' && b[i]>='A') { if (a[i]-32>b[i]) { x=1; break; } else { x=-1; break; } } } } printf("%d\n",x); return 0; }

Codeforces Solutions- 96A Football

Hi friends, In this post I am gonna give you the solution of the codeforces problem: 96A - Football.
The problem screenshot is given below:


/// OmShantihari /// Author: Sujan Mridha /// CSE, University of Barishal #include<stdio.h> #include<string.h> int main() { int i,o,p=0; char n[700]; scanf("%s",&n); o=strlen(n); for (i=0;i<o-6;i++) { if (n[i]=='0' && n[i+1]=='0' && n[i+2]=='0' && n[i+3]=='0' && n[i+4]=='0' && n[i+5]=='0' && n[i+6]=='0') { p=7; break; } if (n[i]=='1' && n[i+1]=='1' && n[i+2]=='1' && n[i+3]=='1' && n[i+4]=='1' && n[i+5]=='1' && n[i+6]=='1') { p=7; break; } } if (p==7) printf("YES\n"); else printf("NO\n"); return 0; }

Solutions Of Codeforces Problem- A Bit++ in C language

Problem screenshot is given Below:

Code:
#include<stdio.h> #include<string.h> int main(){ int i,t,s=0; char x[4]; scanf("%d",&t); for(i=1;i<=t;i++){ scanf("%s",&x); if((strcmp(x,"X++")==0)||(strcmp(x,"++X")==0)){ s=s+1; } else if((strcmp(x,"X--")==0)||(strcmp(x,"--X")==0)){ s=s-1; } s=s; } printf("%d\n",s); return 0; }

Codeforces Problems' Solution (122A - Lucky Division) in C

#include<stdio.h> int main () { int n; scanf("%d", &n); if(((n % 4) == 0) || ((n % 7) == 0) || ((n % 44) == 0) || ((n % 47) == 0) | ((n % 74) == 0) || ((n % 444) == 0) || ((n % 447) == 0) || ((n % 474) == 0) || ((n % 477) == 0)) { printf("YES\n"); } else { printf("NO\n"); } return 0; }

Codeforcces Solution of 50A- Domino Pilling in C language

Codeforcces Solution of 50A Domino Pilling in C language

Hi friends, In this post I'm gonna give you the solution of the codeforces problem 50A - Domino Pilling.
The problem screenshot is given below:

Code:
/// Bismillahir Rahmanir Rahim /// Author: Razinul Karim /// CSE University of Barishal #include<stdio.h> int main() { int N,M,s; scanf("%d%d",&M,&N); if(M>=1 && N<=16) { s=(M*N)/2; } printf("%d",s); return 0; }

  Happy coding!!!

Codeforces Solution of 158-A Next Round in C Language

Hi friends, In this post I am gonna give you the solution of the codeforces problem: 158A - Next Round.
The problem screenshot is given below:

71A - Way Too Long Words -cfsolv

#include<stdio.h> #include<ctype.h> int main(){ int n,i,m; char x[6000]; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%s",&x); int l=strlen(x); if(l>10){ printf("%c",x[0]); printf("%d",l-2); printf("%c\n",x[l-1]); } else printf("%s\n",x);} return 0; }