Optimal DFS Solution in C++, JAVA & PYTHON
Understanding Connected Components in Graphs: A Multi-Language ApproachIntroductionConnected components are a fundamental concept in graph theory, often used in
# Understanding Connected Components in Graphs: A Multi-Language Approach

## Introduction
Connected components are a fundamental concept in graph theory, often used in clustering problems, social network analysis, and recommendation systems. In this blog, we will explore an efficient approach to solving a problem involving connected components using DFS (Depth First Search). We'll implement the solution in **C++, Java, and Python**.

## Problem Statement
Given a list of properties represented as an adjacency matrix, we need to determine the number of connected components based on a similarity threshold **k**. Two nodes (properties) are considered connected if they share at least **k** common attributes.

## Approach
1. **Graph Construction:** Treat properties as nodes and create an edge between two nodes if they share **k** or more attributes.
2. **DFS Traversal:** Use DFS to explore connected nodes and count the number of connected components.
3. **Set Intersection:** Determine common elements between two properties efficiently using a HashSet.

---

## **Java Implementation**
```java
import java.util.*;

class Solution {
    class Edge {
        int src, dest;
        public Edge(int src, int dest) {
            this.src = src;
            this.dest = dest;
        }
    }
    
    public int intersection(int[][] properties, int i, int j) {
        Set<Integer> set = new HashSet<>();
        Set<Integer> setj = new HashSet<>();
        for (int k : properties[j]) setj.add(k);
        for (int k : properties[i]) {
            if (setj.contains(k)) set.add(k);
        }
        return set.size();
    }

    public void dfs(ArrayList<Edge>[] graph, int src, boolean[] visited) {
        visited[src] = true;
        for (Edge e : graph[src]) {
            if (!visited[e.dest]) {
                dfs(graph, e.dest, visited);
            }
        }
    }

    public int numberOfComponents(int[][] properties, int k) {
        int v = properties.length;
        ArrayList<Edge>[] graph = new ArrayList[v];
        for (int i = 0; i < v; i++) graph[i] = new ArrayList<>();

        for (int i = 0; i < v; i++) {
            for (int j = i + 1; j < v; j++) {
                if (intersection(properties, i, j) >= k) {
                    graph[i].add(new Edge(i, j));
                    graph[j].add(new Edge(j, i));
                }
            }
        }

        int count = 0;
        boolean[] visited = new boolean[v];
        for (int i = 0; i < v; i++) {
            if (!visited[i]) {
                count++;
                dfs(graph, i, visited);
            }
        }
        return count;
    }
}
```

---

## **C++ Implementation**
```cpp
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int intersection(vector<vector<int>>& properties, int i, int j) {
        unordered_set<int> setj(properties[j].begin(), properties[j].end());
        int count = 0;
        for (int num : properties[i]) {
            if (setj.count(num)) count++;
        }
        return count;
    }

    void dfs(vector<vector<int>>& graph, vector<bool>& visited, int node) {
        visited[node] = true;
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                dfs(graph, visited, neighbor);
            }
        }
    }

    int numberOfComponents(vector<vector<int>>& properties, int k) {
        int v = properties.size();
        vector<vector<int>> graph(v);

        for (int i = 0; i < v; i++) {
            for (int j = i + 1; j < v; j++) {
                if (intersection(properties, i, j) >= k) {
                    graph[i].push_back(j);
                    graph[j].push_back(i);
                }
            }
        }

        int count = 0;
        vector<bool> visited(v, false);
        for (int i = 0; i < v; i++) {
            if (!visited[i]) {
                count++;
                dfs(graph, visited, i);
            }
        }
        return count;
    }
};
```

---

## **Python Implementation**
```python
def intersection(properties, i, j):
    setj = set(properties[j])
    return len([x for x in properties[i] if x in setj])

def dfs(graph, src, visited):
    visited[src] = True
    for neighbor in graph[src]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)

def number_of_components(properties, k):
    v = len(properties)
    graph = [[] for _ in range(v)]
    
    for i in range(v):
        for j in range(i + 1, v):
            if intersection(properties, i, j) >= k:
                graph[i].append(j)
                graph[j].append(i)
    
    count = 0
    visited = [False] * v
    for i in range(v):
        if not visited[i]:
            count += 1
            dfs(graph, i, visited)
    return count
```

---

## **Time Complexity Analysis**
- **Graph Construction:** O(N² × M), where N is the number of nodes and M is the average length of each property list.
- **DFS Traversal:** O(N + E), where E is the number of edges.
- **Total Complexity:** Approximately **O(N² × M)**.

## **Conclusion**
In this blog, we discussed how to find connected components using DFS across multiple programming languages. The key takeaways are:
- Efficient **set operations** to determine common attributes.
- **DFS traversal** to count connected components.
- **Graph adjacency list representation** to store connections efficiently.

This approach is useful in **clustering, recommendation systems, and social network analysis**. 🚀 Happy Coding!


['Depth-First Search', 'Graph', 'Ordered Set', 'Python', 'C++', 'Java', 'Python3']