✅Simple graph BFS traversal ✅Full explanation
Intuition\n Describe your first thoughts on how to solve this problem. \nGiven problem can be seen as graph problem. Because we have houses as nodes and paths a
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nGiven problem can be seen as graph problem. Because we have houses as nodes and paths as edges. We want to find total pairs of houses with distance equal to 1 to n. This can be achieved easily using BFS traversal of graph. As at each level the distance increases by one.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nCreate adjacency list for given n, x, y.\nCreate array ans to store number of pairs. \nCall BFS from each node and calculate the number of nodes at distance 1, 2, ..., k and increment the ans array accordingly.\n\n# Code\n```Java []\nclass Pair{\n    int first;\n    int second;\n    Pair(int first, int second){\n        this.first = first;\n        this.second = second;\n    }\n}\n\nclass Solution {\n    void BFS(int source, List<List<Integer>> adj, int[] ans, int[] vis){\n        Queue<Pair> q = new LinkedList<>();\n        q.add(new Pair(source, 0));\n        vis[source] = 1;\n        while(!q.isEmpty()){\n            int size = q.size();\n            for(int i=0; i<size; i++){\n                Pair top = q.poll();\n                if(top.second>=1) ans[top.second-1]++;\n                for(int a : adj.get(top.first)){\n                    if(vis[a] == 0){\n                        vis[a] = 1;\n                        q.add(new Pair(a, top.second+1));\n                    }\n                }\n            }\n        }\n    }\n    public int[] countOfPairs(int n, int x, int y) {\n        List<List<Integer>> adj = new ArrayList<>();\n        for(int i=0; i<=n; i++){\n            adj.add(new ArrayList<Integer>());\n        }\n        for(int i=1; i<n; i++){\n            adj.get(i).add(i+1);\n            adj.get(i+1).add(i);\n        }\n        adj.get(x).add(y);\n        adj.get(y).add(x);\n\n        int[] ans = new int[n];\n\n        for(int i=1; i<=n; i++){\n            int[] vis = new int[n+1];\n            BFS(i, adj, ans, vis);\n        }\n        return ans;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    void BFS(int source, vector<vector<int>>& adj, vector<int>& ans, vector<int>& vis) {\n        queue<pair<int, int>> q;\n        q.push(pair(source, 0));\n        vis[source] = 1;\n        \n        while (!q.empty()) {\n            int size = q.size();\n            for (int i = 0; i < size; i++) {\n                pair top = q.front();\n                q.pop();\n                if (top.second >= 1) {\n                    ans[top.second - 1]++;\n                }\n                for (int a : adj[top.first]) {\n                    if (vis[a] == 0) {\n                        vis[a] = 1;\n                        q.push(pair(a, top.second + 1));\n                    }\n                }\n            }\n        }\n    }\n\n    vector<int> countOfPairs(int n, int x, int y) {\n        vector<vector<int>> adj(n + 1, vector<int>());  \n        for (int i = 1; i < n; i++) {\n            adj[i].push_back(i + 1);\n            adj[i + 1].push_back(i);\n        }\n        adj[x].push_back(y);\n        adj[y].push_back(x);\n\n        vector<int> ans(n, 0);\n        for (int i = 1; i <= n; i++) {\n            vector<int> vis(n + 1, 0);\n            BFS(i, adj, ans, vis);\n        }\n\n        return ans;\n    }\n};\n```\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    Creating adjacency list : O(n)  \n    For BFS we have n nodes and atmost n edges so\n    For BFS T. C. : O(n + n) = O(n)\n    and we are calling BFS from n nodes\n    therefore overall \n    Time Complexity = O(n) + O(n^2) = O(n^2)    \n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    For adjacency list : O(n);\n    For Queue : O(n);\n\nConsider upvoting!!!\n
['Breadth-First Search', 'Graph', 'C++', 'Java']