C++ Simple Solution With Explanation Using Bitmask & Floyd Warshall Algorithm - O(2^N*N^2)
Firstly, we will use Floyd Warshall Algorithm to find the distance between every pair of nodes. Its time complexity will be O(N^3) \nHere, N is 15 so we can con
Firstly, we will use Floyd Warshall Algorithm to find the distance between every pair of nodes. Its time complexity will be O(N^3) \nHere, N is 15 so we can consider every possible subset in O(2^N) and then\n1) check if it is a subtree: if it is a subtree then no of nodes (cities) - 1 = no of edges\n2) find the maximum distance between any two cities by the use of two loops i and j & finding max distance between cities i and j in O(N^2)\n```\nclass Solution {\npublic:\n    int findDist(int bitmask, vector<vector<int>> &dist) {\n        int numCities = 0, numEdges = 0, maxDist = 0;\n        for(int i=0; i<dist.size(); i++) {\n            if(((bitmask>>i)&1) == 0) continue; // skip if city i is not in subset\n            numCities++;\n            for(int j=i+1; j<dist.size(); j++) {\n                if(((bitmask>>j)&1) == 0) continue; // skip if city j is not in subset\n                numEdges += dist[i][j] == 1;\n                maxDist = max(maxDist, dist[i][j]);\n            }\n        }\n        if(numEdges != numCities - 1) maxDist = 0; // if no of edges not equal to no of cities - 1 then our subset is not a subtree so we return 0;\n        return maxDist;\n    }\n    \n    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {\n        vector<vector<int>> dist(n, vector<int> (n, n)); // dist[i][j] represent distance between nodes i and j which can be max n\n        for(auto &e: edges) // updating distance between nodes that have an edge connecting them\n            dist[e[0]-1][e[1]-1] = dist[e[1]-1][e[0]-1] = 1; \n        \n        for(int k=0; k<n; k++) // using floyd warshall algorithm to update distances\n            for(int i=0; i<n; i++)\n                for(int j=0; j<n; j++)\n                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); \n        \n        vector<int> ans(n-1, 0);\n        for(int bitmask = 0; bitmask < (1<<n); bitmask++) {\n            int maxDist = findDist(bitmask, dist); // finding min distance between two nodes in the subset\n            if(maxDist > 0) ans[maxDist-1]++;\n        }\n        return ans;\n    }\n};\n```
['C', 'Bitmask']