Bitmasking + Dijkstra's
Approach\n Describe your approach to solving the problem. \nI solved this problem in 3 parts.\n1. Create a Tree.\n2. Get all possible subsets using bitmasking.\
# Approach\n<!-- Describe your approach to solving the problem. -->\nI solved this problem in 3 parts.\n1. Create a Tree.\n2. Get all possible subsets using bitmasking.\n3. Check if the subset form a connected component or not. If yes, For each node in subset as source, get the maximum distance. Update it in the output list and return ans\n\nI solved the getting the maximum distance part using Dijkstra\'s.\nFor each node in subset, get the maximum distance for each node as source. \nWhenever the nodes traversed in Dijkstra\'s are less than no of nodes in subset, we know this is not a connected component. We skip this subset.\nIf the given subset forms a connected component, we find the maximum possible distance and update the result.\n\n# Code\n```\nclass Solution:\n    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n        tree=defaultdict(list)\n        for u,v in edges:\n            tree[u].append(v)\n            tree[v].append(u)\n        def getDistances(src,nodes):\n            heap=[[0,src]]\n            minCost={}\n            res=0\n            while heap:\n                cost,node=heappop(heap)\n                if node in minCost:\n                    continue\n                minCost[node]=cost\n                if cost>res: res=cost\n                for nei in tree[node]:\n                    if nei not in minCost and nei in nodes:\n                        heappush(heap,[1+cost,nei])\n            if len(minCost)!=len(nodes): return [False,0]\n            return [True,res]\n        d=[0]* (n-1)\n        for mask in range(1,2**n):\n            nodes=set()\n            for j in range(n):\n                if mask & (1<<j):\n                    nodes.add(j+1)\n            res=0\n            if len(nodes)>1:\n                for i in nodes:\n                    decide,val=getDistances(i,nodes)\n                    if not decide: break \n                    res=max(res,val)\n                else: \n                    d[res-1]+=1\n        return d\n```
['Shortest Path', 'Bitmask', 'Python3']