Fastest C++ solution, beats 100%, smart brute force
Intuition\n Describe your first thoughts on how to solve this problem. \n\n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Tim
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n![Screen Shot 2023-07-30 at 10.57.02 PM.png](https://assets.leetcode.com/users/images/aa5fd0dd-33fc-4bdc-8853-654ac3f0d7c2_1690729046.8373163.png)\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(n^2 2^{n})$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n^2)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    // edges[i] is the neighbors of i\n    vector<int> edges[16];\n    // dists[i][j] is the dist between i and j\n    int dists[16][16]{};\n    // masks[i][j] is the mask of cities visited when going from i to j\n    int masks[16][16]{};\n    struct Data {\n        int city;\n        int dist;\n        int mask;\n    };\npublic:\n    // do BFS starting at curCity\n    void getCities(int curCity) {\n        static std::deque<Data> q;\n        static std::array<bool, 16> visited;\n        visited.fill(false);\n        q.clear();\n        q.emplace_back(Data{curCity, 0, 1 << curCity});\n        visited[curCity] = true;\n        while (q.size()) {\n            Data d = q.front();\n            q.pop_front();\n            for (auto neighbor : edges[d.city]) {\n                if (!visited[neighbor]) {\n                    q.emplace_back(Data{neighbor, d.dist + 1, d.mask | (1<<(neighbor))});\n                    visited[neighbor] = true;\n                    dists[neighbor][curCity] = dists[curCity][neighbor] = d.dist + 1;\n                    masks[neighbor][curCity] = masks[curCity][neighbor] = q.back().mask;\n                }\n            }\n        }\n    }\n\n    vector<int> countSubgraphsForEachDiameter(const int n, vector<vector<int>>& ed) {\n        for (const auto& pair: ed) {\n            edges[pair[0] - 1].emplace_back(pair[1] - 1);\n            edges[pair[1] - 1].emplace_back(pair[0] - 1);\n        }\n        std::vector<int> ans(n - 1, 0);\n        for (int j = 0; j < n; ++j) { // curCity\n            getCities(j);\n        }\n        // loop thru every possible subset \n        for (int mask = 1; mask < (1 << n); ++mask) {\n            int maxDist = 0;\n            for (int i = 0; i < n; i++) {\n                if ((mask & (1 << i)) == 0) continue;\n                for (int j = 0; j < i; j++) {\n                    // check i and j are reachable within the subset \n                    if (mask & (1 << j)) {\n                        if(dists[i][j]==0 || (masks[i][j] & mask) != masks[i][j] ) {i=j=n;maxDist=0;break;}\n                        maxDist = std::max(maxDist, dists[i][j]);\n                    }\n                }\n            }\n            if (maxDist) ans[maxDist-1]++;\n        }\n        return ans;\n    }\n};\n```
['Bit Manipulation', 'Breadth-First Search', 'Graph', 'Bitmask', 'C++']