DFS Problem With Solution

Connected Components in an Undirected Graph

Problem -1

Given an undirected graph with N vertices and M Medges, find the number of connected components.

Code:

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

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

void dfs(int node) {
    visited[node] = true;

    for (int next : adj[node]) {
        if (!visited[next]) {
            dfs(next);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int components = 0;

    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i);
            components++;
        }
    }

    cout << components << endl;

    return 0;
}

Cycle Detection in an Undirected Graph

Problem-2

Determine whether an undirected graph contains a cycle.

Code:

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

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

bool dfs(int node, int parent) {
    visited[node] = true;

    for (int next : adj[node]) {
        if (!visited[next]) {
            if (dfs(next, node))
                return true;
        }
        else if (next != parent) {
            return true;
        }
    }

    return false;
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    bool cycle = false;

    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            if (dfs(i, -1)) {
                cycle = true;
                break;
            }
        }
    }

    if (cycle)
        cout << "Cycle Found" << endl;
    else
        cout << "No Cycle" << endl;

    return 0;
}