🔥O(n^2) - BFS - Dist Vector | Clean Code | C++ |
Code\n\nclass Solution {\npublic:\n    vector<int> bfs(int src, int n, unordered_map<int, vector<int>>& adjlist)\n    {\n        queue<int> q;\n        q.push(s
# Code\n```\nclass Solution {\npublic:\n    vector<int> bfs(int src, int n, unordered_map<int, vector<int>>& adjlist)\n    {\n        queue<int> q;\n        q.push(src);\n\n        set<int> visit;\n        visit.insert(src);\n\n        int len = 0;\n        vector<int> dist(n + 1, 0);\n\n        while (!q.empty())\n        {\n            int sz = q.size();\n            for (int i = 0; i < sz; i++)\n            {\n                auto curr = q.front();\n                q.pop();\n\n                dist[len]++;\n\n                for (auto neigh: adjlist[curr])\n                {\n                    if (visit.find(neigh) != visit.end())\n                        continue;\n                    \n                    q.push(neigh);\n                    visit.insert(neigh);\n                }\n            }\n\n            len++;\n        }\n\n        return dist;\n    }\n    vector<int> countOfPairs(int n, int x, int y) {\n        unordered_map<int, vector<int>> adjlist;\n        for (int i = 1; i < n; i++)\n        {\n            adjlist[i].push_back(i + 1);\n            adjlist[i + 1].push_back(i);\n        }\n\n        adjlist[x].push_back(y);\n        adjlist[y].push_back(x);\n\n\n        vector<int> res(n, 0);\n        for (int i = 1; i <= n; i++)\n        {\n            vector<int> tmp = bfs(i, n, adjlist);\n            \n            for (int i = 0; i < n; i++)\n            {\n                res[i] += tmp[i + 1];\n            }\n        }\n\n        return res;\n    }\n};\n```
['C++']