BFS made easy
Intuition\nThe problem involves calculating the number of node pairs at various distances in a graph. To efficiently solve this, I decided to represent the grap
# Intuition\nThe problem involves calculating the number of node pairs at various distances in a graph. To efficiently solve this, I decided to represent the graph as an adjacency list and use Breadth-First Search (BFS) to traverse it. BFS is ideal because it explores nodes level by level, which directly corresponds to the distances needed.\n\n# Approach\n1. **Graph Representation**:\n   - Create an adjacency list for the graph, initializing each node with an empty list of neighbors.\n   - Add the special edge between nodes `x` and `y` to the adjacency list.\n   - Build the remaining graph structure by connecting consecutive nodes.\n\n2. **Traversal with BFS**:\n   - For each node in the graph, perform a BFS starting from that node.\n   - Use a queue to explore neighbors and a `visited` set to avoid revisiting nodes.\n   - Maintain a distance counter (`d`) and update the result list `res` to store the count of node pairs at each distance.\n\n3. **Result Accumulation**:\n   - At the end of BFS from all nodes, the `res` array contains the count of node pairs for each distance.\n\n# Complexity\n- **Time Complexity**:\n  - Constructing the graph takes $$O(n)$$.\n  - Each BFS traversal processes all edges, resulting in a total of $$O(n^2)$$ for all nodes.\n  - Overall time complexity: $$O(n^2)$$.\n  \n- **Space Complexity**:\n  - The adjacency list requires $$O(n)$$ space.\n  - The BFS queue and `visited` set take $$O(n)$$ space.\n  - Overall space complexity: $$O(n)$$.\n\n\n# Code\n```python3 []\nclass Solution:\n    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:\n        graph = { i+1:[] for i in range(n)}\n        graph[x].append(y)\n        graph[y].append(x)\n        for i in range(n-1):\n            graph[i+1].append(i+2)\n            graph[i+2].append(i+1)\n        print(graph)\n        self.res = [0]*n\n        def bfs(node):\n            q, visited, d = deque(), set(), 0\n            q.append(node)\n            visited.add(node)\n            while q:\n                for i in range(len(q)):\n                    left_node = q.popleft()\n                    for nei in graph[left_node]:\n                        if nei not in visited:\n                            self.res[d] += 1\n                            q.append(nei)\n                            visited.add(nei)\n                d += 1\n        for i in range(n):\n            bfs(i+1)\n        return self.res\n```
['Python3']