Dfs program in c++

#include <iostream>
#include <vector>
using namespace std;

vector<int> adj[100001];
bool visited[100001];

void dfs(int v) {
    visited[v] = true;
    cout << v << " ";
    for (int u : adj[v]) {
        if (!visited[u]) {
            dfs(u);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }
    return 0;
}

Explanation of the DFS Program in C++

• The program begins by including the necessary libraries and declaring the namespace.

• A vector of integers, adj, of size 100001, and a boolean array, visited, of size 100001 are declared.

• The dfs function is defined to perform the depth-first search. It takes an integer v as its parameter.

• Inside the dfs function, the node v is marked as visited, and its value is printed.

• It then iterates through the adjacent nodes of v using a range-based for loop and recursively calls the dfs function for unvisited adjacent nodes.

• In the main function, it reads the number of nodes n and edges m from the standard input.

• Then, it reads the edges and populates the adjacency list adj accordingly.

• Finally, it iterates through all nodes and calls the dfs function for each unvisited node.

• The program ends by returning 0 to indicate successful execution.