Microsoft⭐ || Easy Solution🔥|| BEATS 100%✅
#ReviseWithArsh #6Companies30Days challenge 2k24\nCompany 2 :- Google\n\n# Code\n\nclass Solution {\n    vector<int> edges[16];  // edges[i] stores the neighbor
***#ReviseWithArsh #6Companies30Days challenge 2k24\nCompany 2 :- Google***\n\n# Code\n```\nclass Solution {\n    vector<int> edges[16];  // edges[i] stores the neighbors of city i\n    int dists[16][16]{};    // dists[i][j] stores the distance between city i and city j\n    int masks[16][16]{};    // masks[i][j] stores the mask of cities visited when going from i to j\n    struct Data {\n        int city;\n        int dist;\n        int mask;\n    };\npublic:\n    // Perform BFS starting at the current city\n    void bfs(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.empty()) {\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        vector<int> ans(n - 1, 0);  // Initialize answer array\n        // Calculate distances and masks for each city\n        for (int j = 0; j < n; ++j) {\n            bfs(j);\n        }\n        // Loop through every possible subset of cities\n        for (int mask = 1; mask < (1 << n); ++mask) {\n            int maxDist = 0;\n            // Check distances between pairs of cities in the subset\n            for (int i = 0; i < n; i++) {\n                if (!(mask & (1 << i))) continue;\n                for (int j = 0; j < i; j++) {\n                    if (mask & (1 << j)) {\n                        // Check if city i and city j are reachable within the subset\n                        if (dists[i][j] == 0 || (masks[i][j] & mask) != masks[i][j]) {\n                            i = j = n;  // Break the loop\n                            maxDist = 0;\n                            break;\n                        }\n                        maxDist = std::max(maxDist, dists[i][j]);\n                    }\n                }\n            }\n            if (maxDist) ans[maxDist - 1]++;\n        }\n        return ans;\n    }\n};\n\n```
['C++']