Brute force checking all subgraphs with neat bfs trick to find diameter
The solution consists of the following steps:\n1. Use bit-masking to generate all possible subgraphs\n2. For each subgraph, bfs to check if it is connected (and
The solution consists of the following steps:\n1. Use bit-masking to generate all possible subgraphs\n2. For each subgraph, `bfs` to check if it is connected (and therefore a subtree); \n3. For each subtree, do a `bfs` again to compute its diameter.\n\nThe way I compute the diameter is based on the following theorem:\nFor any given node `a` of the tree, a farthest node `b` from `a` must be one of the end points of a path with maximal length. i.e. there exists a path from `b` to `c` whose length is maximal. \nUsing this fact, when we do the first `bfs` with a random root, we find `b`. Then we do another `bfs` with `b` as the root to find `c` and the corresponding diameter of the tree. \n\nBelow are my codes:\n\n```\nclass Solution:\n    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n        graph = collections.defaultdict(list)\n        for a, b in edges:\n            graph[a-1] += [b-1]\n            graph[b-1] += [a-1]\n            \n        def bfs(root, nodes, k):\n            s = [root]\n            seen = set(s)\n            d = -1\n            while s:\n                d += 1\n                new_s = []\n                for node in s:\n                    new_s += [x for x in graph[node] if (1 << x) & nodes and x not in seen]\n                if not new_s:\n                    far = s[0]\n                s = new_s\n                seen = seen.union(new_s)\n            if len(seen) != k:\n                return root, float("inf")\n            return far, d\n        def find(nodes):\n            i = next(i for i in range(n) if (1 << i) & nodes)\n            k = bin(nodes).count("1")\n            far, d = bfs(i, nodes, k)\n            if d == float("inf"):\n                return 0\n            _, d = bfs(far, nodes, k)\n            return d\n        ans = [0]*n\n        for i in range(1, 1 << n):\n            ans[find(i) - 1] += 1\n        ans.pop()\n        return ans\n```\nTime Complexity: `O(n*2^n)`
['Breadth-First Search', 'Bitmask']