C++ Two Approaches
I overdid this one - wasted a lot of time trying to find a practical approach. Instead, I should have focused on the brute-force... I checked constraints this t
I overdid this one - wasted a lot of time trying to find a practical approach. Instead, I should have focused on the brute-force... I checked constraints this time, but was still stuborn somehow.\n \n We enumerate all combinations of nodes (up to 2 ^ 16 combinations), then check if these nodes form a tree. If they do, get the diameter of the tree. Track and return the count of each diameter.\n\n#### Approach 1: DFS\nWe first build an adjacency list. Then, we enumerate all possible combinations of nodes. For each combination, we pick a node and do DFS. While doing DFS, we calculate the tree diameter, and also count nodes. We count nodes to make sure that all nodes in the combination were reached, so they form a tree.\n\n```cpp\nint dfs(vector<vector<int>> &al, int mask, int i, int &n, int &res) {\n    int dia = 0, max_dia = 0;\n    ++n;\n    for (auto j : al[i])\n        if (mask & (1 << j)) {\n            int dia = 1 + dfs(al, mask ^ (1 << j), j, n, res);\n            res = max(res, dia + max_dia);\n            max_dia = max(max_dia, dia);\n        }\n    return max_dia;\n}\nvector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {\n    vector<vector<int>> al(n);\n    for (auto &e : edges) {\n        al[e[0] - 1].push_back(e[1] - 1);\n        al[e[1] - 1].push_back(e[0] - 1);\n    }\n    vector<int> res(n - 1);\n    for (int s = 3; s < 1 << n; ++s) {\n        for (int i = 0; i < n; ++i)\n            if (s & (1 << i)) {\n                int nodes = 0, dia = 0;\n                dfs(al, s ^ (1 << i), i, nodes, dia);\n                if (dia > 0 && nodes == bitset<16>(s).count())\n                    ++res[dia - 1];\n                break;\n            }\n    }\n    return res;\n}\n```\n**Complexity Analysis**\n- Time: O(n * 2 ^ n). We enumerate 2 ^ n trees and traverse each tree once.\n- Memory: O(n). Because it\'s a tree, the number of edges is n - 1, so we our adjacency list need 2n -1 space.\n\n#### Approach 2: Floyd-Warshall\nThis approach is more complicated and a bit slower. Here, we first build an adjacency matrix with the distance between each node using Floyd-Warshall algorithm O(n ^ 3).\n\nThen, instead of doing DFS, we enumerate all pairs of nodes, and lookup the distance in the adjacency matrix. We also need to count the edges (`d[i][j] == 1`) to make sure all these nodes are in the same subtree (`nodes == edges - 1`).\n\n```cpp\nvector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {\n    vector<vector<int>> d(n, vector<int>(n, n));\n    for (auto &e : edges)\n        d[e[0] - 1][e[1] - 1] = d[e[1] - 1][e[0] - 1] = 1;\n    for (int k = 0; k < n; ++k)\n        for (int i = 0; i < n; ++i)\n            for (int j = 0; j < n; ++j)\n                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);\n    vector<int> res(n - 1, 0);\n    for (int s = 0; s < 1 << n; ++s) {\n        int max_depth = 0, nodes = 0, edges = 0;\n        for (int i = 0; i < n; ++i)\n            if (s & (1 << i)) {\n                ++nodes;\n                for (int j = i + 1; j < n; ++j)\n                    if (s & (1 << j)) {\n                        edges += d[i][j] == 1;\n                        max_depth = max(max_depth, d[i][j]);\n                    }\n            }\n        if (edges == nodes - 1 && max_depth > 0)\n            ++res[max_depth - 1];\n    }\n    return res;\n}\n```\n**Complexity Analysis**\n- Time: O(n ^ 2 * 2 ^ n). We enumerate 2 ^ n trees, and enumerate all pairs of nodes.\n- Memory: O(n ^ 2) for the adjacency matrix.
[]