Description

Submission

class Solution {
    vector<vector<int>> adj;
public:
    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {
        adj.resize(n);
        for(auto edge: edges) {
            adj[edge[0]-1].push_back(edge[1]-1);
            adj[edge[1]-1].push_back(edge[0]-1);
        }

        vector<int> allow(n);
        vector<int> dist(n);
        vector<int> count(n, 0);
        for(int state = 0; state < (1<<n); ++state) {
            int nNodes = 0;
            int A = 0;
            for(int i = 0; i < n; ++i) {
                if(((state>>i)&1)==1) {
                    allow[i]=1;
                    A = i;
                    nNodes++;
                }
                else allow[i]=0;
            }
            for(int i = 0; i < n; ++i) dist[i] = -1;
            int B = bfs(A, dist, allow);
            int nVisited = 0;
            for(int i = 0; i < n; ++i) nVisited += (dist[i] != -1);
            if(nVisited != nNodes) continue;
            for(int i = 0; i < n; ++i) dist[i] = -1;
            int C = bfs(B, dist, allow);

            int maxDiameter = *max_element(dist.begin(), dist.end());
            count[maxDiameter]++;
        }
        count.erase(count.begin());
        return count;
    }

    int bfs(int start, vector<int>& dist, vector<int>& allow) {
        queue<int> q;
        q.push(start);
        dist[start] = 0;

        int maxDistance = 0;
        int maxId = start;
        while(!q.empty()) {
            int cur = q.front();
            q.pop();
            for(auto next: adj[cur]) {
                if(allow[next] == 0) continue;
                if(dist[next] == -1) {
                    dist[next] = dist[cur] + 1;
                    if(dist[next] > maxDistance) {
                        maxDistance = dist[next];
                        maxId = next;
                    }
                    q.push(next);
                }
            }
        }
        return maxId;
    }
};

References

1. https://github.com/wisdompeak/LeetCode/blob/master/BFS/1617.Count-Subtrees-With-Max-Distance-Between-Cities/1617.Count-Subtrees-With-Max-Distance-Between-Cities.cpp