100% Beats BFS Optimal Solution in JAVA,C++ & Python
Counting Nodes at Distance k in a Graph \uD83C\uDF10\n\nIn graph theory, a graph is a set of nodes connected by edges, and often we need to perform certain task
## Counting Nodes at Distance `k` in a Graph \uD83C\uDF10\n\nIn graph theory, a **graph** is a set of nodes connected by edges, and often we need to perform certain tasks based on the distance between nodes. For instance, one task might be to count the number of nodes within a certain distance from a given node. Let\'s explore a solution to count the number of nodes within distance `k` in an undirected graph using BFS (Breadth-First Search).\n\n### Problem Overview \uD83E\uDD14\nGiven two graphs represented by edge lists (`edges1` and `edges2`), we need to:\n1. Count how many nodes are at a distance of `k` from each node in the graph.\n2. Find the node with the maximum count of reachable nodes at distance `k` and combine the results from both graphs.\n\nThis problem requires BFS traversal to explore nodes within a specified distance from the starting node.\n\n### Steps to Solve \uD83D\uDCC8\n1. **Create the Graph**: The graph is represented as an adjacency list. We will build the graph from the given edges.\n2. **BFS Traversal**: For each node, we use BFS to explore the nodes within the given distance `k`. During the traversal, we keep track of the distances of nodes from the start node.\n3. **Counting Nodes**: We count how many nodes are at a distance less than or equal to `k`.\n4. **Combine Results**: We combine the results of the two graphs and return the final node counts.\n\n### Solution \uD83D\uDCBB\n\n```java []\nimport java.util.*;\n\nclass Solution {\n    class edge {\n        int src, dest;\n        public edge(int src, int dest) {\n            this.src = src;\n            this.dest = dest;\n        }\n    }\n\n    public void createGraph(ArrayList<edge>[] graph, int[][] edges) {\n        for (int i = 0; i < graph.length; i++) {\n            graph[i] = new ArrayList<>();\n        }\n        for (int[] e : edges) {\n            int src = e[0];\n            int dest = e[1];\n            graph[src].add(new edge(src, dest));\n            graph[dest].add(new edge(dest, src)); // Since it\'s undirected\n        }\n    }\n\n    public int countNodesWithinDistanceK(ArrayList<edge>[] graph, int startNode, int k) {\n        Queue<Integer> queue = new LinkedList<>();\n        boolean[] visited = new boolean[graph.length];\n        int[] distance = new int[graph.length];\n\n        queue.add(startNode);\n        visited[startNode] = true;\n\n        int count = 0; // To count nodes within distance <= k\n\n        while (!queue.isEmpty()) {\n            int current = queue.poll();\n            if (distance[current] <= k) {\n                count++;\n            }\n\n            for (edge e : graph[current]) {\n                if (!visited[e.dest]) {\n                    queue.add(e.dest);\n                    visited[e.dest] = true;\n                    distance[e.dest] = distance[current] + 1;\n                }\n            }\n        }\n\n        return count;\n    }\n\n    public void count(ArrayList<edge>[] graph, int k, int[] res) {\n        for (int i = 0; i < graph.length; i++) {\n            res[i] = countNodesWithinDistanceK(graph, i, k);\n        }\n    }\n\n    public int[] maxTargetNodes(int[][] edges1, int[][] edges2, int k) {\n        Set<Integer> node1 = new HashSet<>();\n        Set<Integer> node2 = new HashSet<>();\n        \n        // Fill the sets with nodes from both graphs\n        for (int[] edge : edges1) {\n            node1.add(edge[0]);\n            node1.add(edge[1]);\n        }\n        for (int[] edge : edges2) {\n            node2.add(edge[0]);\n            node2.add(edge[1]);\n        }\n\n        ArrayList<edge>[] graph1 = new ArrayList[node1.size()];\n        ArrayList<edge>[] graph2 = new ArrayList[node2.size()];\n\n        createGraph(graph1, edges1);\n        createGraph(graph2, edges2);\n\n        int[] count1 = new int[graph1.length];\n        int[] count2 = new int[graph2.length];\n        \n        count(graph1, k, count1);\n        count(graph2, k - 1, count2);  // For second graph, we reduce the distance by 1\n\n        int max = Integer.MIN_VALUE;\n        for (int i = 0; i < count2.length; i++) {\n            max = Math.max(max, count2[i]); // Find the maximum count from the second graph\n        }\n\n        int[] res = new int[graph1.length];\n        for (int i = 0; i < count1.length; i++) {\n            res[i] = count1[i] + max;  // Combine results from both graphs\n        }\n\n        return res;\n    }\n}\n```\n```cpp []\n#include <iostream>\n#include <vector>\n#include <queue>\n#include <unordered_set>\n#include <algorithm>\n\nusing namespace std;\n\nclass Solution {\npublic:\n    struct Edge {\n        int src, dest;\n        Edge(int src, int dest) : src(src), dest(dest) {}\n    };\n\n    void createGraph(vector<Edge> graph[], vector<vector<int>>& edges) {\n        for (auto& e : edges) {\n            int src = e[0], dest = e[1];\n            graph[src].push_back(Edge(src, dest));\n            graph[dest].push_back(Edge(dest, src));\n        }\n    }\n\n    int countNodesWithinDistanceK(vector<Edge> graph[], int startNode, int k, int n) {\n        vector<bool> visited(n, false);\n        vector<int> distance(n, -1);\n        queue<int> q;\n        q.push(startNode);\n        visited[startNode] = true;\n        distance[startNode] = 0;\n\n        int count = 0;\n        while (!q.empty()) {\n            int current = q.front();\n            q.pop();\n\n            if (distance[current] <= k) {\n                count++;\n            }\n\n            for (auto& e : graph[current]) {\n                if (!visited[e.dest]) {\n                    visited[e.dest] = true;\n                    distance[e.dest] = distance[current] + 1;\n                    q.push(e.dest);\n                }\n            }\n        }\n        return count;\n    }\n\n    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {\n        unordered_set<int> node1, node2;\n        for (auto& e : edges1) {\n            node1.insert(e[0]);\n            node1.insert(e[1]);\n        }\n        for (auto& e : edges2) {\n            node2.insert(e[0]);\n            node2.insert(e[1]);\n        }\n\n        int n1 = node1.size(), n2 = node2.size();\n        vector<Edge> graph1[n1], graph2[n2];\n\n        createGraph(graph1, edges1);\n        createGraph(graph2, edges2);\n\n        vector<int> count1(n1), count2(n2);\n        for (int i = 0; i < n1; i++) {\n            count1[i] = countNodesWithinDistanceK(graph1, i, k, n1);\n        }\n        for (int i = 0; i < n2; i++) {\n            count2[i] = countNodesWithinDistanceK(graph2, i, k - 1, n2);\n        }\n\n        int max = *max_element(count2.begin(), count2.end());\n        vector<int> res(n1);\n        for (int i = 0; i < n1; i++) {\n            res[i] = count1[i] + max;\n        }\n        return res;\n    }\n};\n```\n```python []\nfrom collections import deque\n\nclass Solution:\n    class Edge:\n        def __init__(self, src, dest):\n            self.src = src\n            self.dest = dest\n\n    def createGraph(self, graph, edges):\n        for e in edges:\n            src, dest = e\n            graph[src].append(self.Edge(src, dest))\n            graph[dest].append(self.Edge(dest, src))  # Since it\'s undirected\n\n    def countNodesWithinDistanceK(self, graph, startNode, k):\n        visited = [False] * len(graph)\n        distance = [-1] * len(graph)\n        queue = deque([startNode])\n        visited[startNode] = True\n        distance[startNode] = 0\n\n        count = 0\n        while queue:\n            current = queue.popleft()\n\n            if distance[current] <= k:\n                count += 1\n\n            for e in graph[current]:\n                if not visited[e.dest]:\n                    visited[e.dest] = True\n                    distance[e.dest\n\n] = distance[current] + 1\n                    queue.append(e.dest)\n        return count\n\n    def maxTargetNodes(self, edges1, edges2, k):\n        node1, node2 = set(), set()\n        for e in edges1:\n            node1.update(e)\n        for e in edges2:\n            node2.update(e)\n\n        graph1 = [[] for _ in range(len(node1))]\n        graph2 = [[] for _ in range(len(node2))]\n\n        self.createGraph(graph1, edges1)\n        self.createGraph(graph2, edges2)\n\n        count1 = [self.countNodesWithinDistanceK(graph1, i, k) for i in range(len(graph1))]\n        count2 = [self.countNodesWithinDistanceK(graph2, i, k - 1) for i in range(len(graph2))]\n\n        maxCount = max(count2)\n        res = [count1[i] + maxCount for i in range(len(count1))]\n        return res\n```\n\n\n### Explanation of Code \uD83D\uDCDC\n\n1. **Graph Representation**: We create a graph using an adjacency list. Each node has a list of edges connected to it.\n2. **`countNodesWithinDistanceK()` Method**:\n   - We start a BFS traversal from a given `startNode`.\n   - As we traverse, we calculate the distance from the start node for each other node.\n   - If a node\u2019s distance is less than or equal to `k`, we increment the count.\n3. **`count()` Method**:\n   - This method counts the nodes within distance `k` for each node in the graph.\n4. **`maxTargetNodes()` Method**:\n   - We combine results from two different graphs (`edges1` and `edges2`) by first counting the nodes within distance `k` for each node in both graphs, and then adding the maximum result from the second graph to the first graph.\n\n### Conclusion \uD83C\uDFC1\n\nThis blog demonstrated a solution to count the number of nodes within distance `k` in a graph. The approach uses BFS to traverse the graph and counts nodes within the given distance range. We discussed the solution in **Java**, **C++**, and **Python**, with the added benefit of clear explanations and emojis for a fun, engaging read! \uD83D\uDE80
['Breadth-First Search', 'Graph', 'Python', 'C++', 'Java', 'Python3']