[C++] Graph + Bitmask + BFS || 24ms || O(n*n*(2^n))
Logic:\nAs we form an undirected tree. We can represent a set of cities in bits. \nWe will only consider those set of the city which will be connected and ignor
Logic:\nAs we form an undirected tree. We can represent a set of cities in bits. \nWe will only consider those set of the city which will be connected and ignore non-connected cities.\nAt some position, we take a set of connected cities and represent it in binary as 001101, then we can say city 1, city 3, city 4 are connected and have a value of max distance in that set.\nNow what we want is to add a new city into that set. We can add a new city if we have one node in the current set and the other node (suppose city 2) of edge is not in the current set. Then we can create a new set which is 001111. Finally, we need to find the max distance in this set. There will be a maximum of 2 cases:\n\t1. It will be the same as the current set.\n\t2. If we do a dfs from the new city and visit only those cities which are in curr set.\nFinally, we get the maximum distance in the new set, then we will update it the answer array.\n\nTo work with the set more conveniently, I use the queue data structure in which I initialize it with a singleton set representing each city. Then I take the front set of the queue and then create a new set and push it into the queue.\n\n```\nclass Solution {\npublic:\n    vector<list<int>> adjList;\n    // finding the max distance from new city inside the curr set of cities\n    int dfs(int src, int parent, int mask){\n        int maxDist=-1;\n        for(auto dest: adjList[src]){\n            if(dest == parent)  continue;\n            if(mask&(1<<dest))  maxDist = max(maxDist, dfs(dest, src, mask));\n        }\n        return maxDist+1;\n    }\n    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {\n        adjList.resize(n, list<int>()) ;\n        for(auto e:edges){\n            adjList[e[0]-1].push_back(e[1]-1);\n            adjList[e[1]-1].push_back(e[0]-1);\n        }\n        vector<int> ans(n-1);\n        vector<int> memo((1<<n), -1);   // will store max distance in set of cities\n        queue<int> q;\n        for(int i=0; i<n; i++)  memo[1<<i]=0, q.push(1<<i);\n        while(!q.empty()){\n            int currSet = q.front();   q.pop();\n            for(int i=0; i<n; i++){\n                // considering city which is in curr set\n                if(currSet & (1<<i)){\n                    for(auto d: adjList[i]){                        \n                        if(currSet & (1<<d))   continue;\n                        int newSet = (currSet|(1<<d));\n                        if(memo[newSet]>=0) continue;\n                        // new city doesnot included in set and the new set formed is unvisited\n                        memo[newSet] = max(memo[currSet], dfs(d, -1, currSet));\n                        ans[memo[newSet]-1]++;\n                        q.push(newSet);\n                    }\n                }\n            }\n        }\n        return ans;\n    }\n};\n```\n\nTime Complexity: \nO(n * n * (2^n))\nAs we are considering all possible set which will be (2^n) and for each set we are checking all edges which can be formed in that set in n*n .
['Depth-First Search', 'Breadth-First Search', 'C', 'Bitmask']