Posted on

## 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