Problem
There's an oriented graph (not necessarily a strongly connected one). The number of nodes n
and edges m
in it don't exceed 50000
. Find a reachability matrix for it.
My Effort
I've come up with a recursive DFS solution such that for every node in the graph I update the reachability matrix for it and nodes reachable from it. Here it is:
...
void recursiveDfs(uint16_t node,
std::unordered_map<uint16_t, std::unordered_set<uint16_t>>& reachabilityMatrix,
std::unordered_map<uint16_t, std::unordered_set<uint16_t>>& adjacentNodes) {
std::unordered_set<uint16_t> reachableNodes = reachabilityMatrix[node];
for (const auto& adjacentNode : adjacentNodes[node]) {
if (!reachableNodes.count(adjacentNode)) {
reachableNodes.insert(adjacentNode);
recursiveDfs(adjacentNode, reachabilityMatrix, adjacentNodes);
}
reachableNodes.insert(reachabilityMatrix[adjacentNode].begin(), reachabilityMatrix[adjacentNode].end());
}
}
int main() {
...
// find the reachability matrix
for (int i = 1; i <= n; i++) {
recursiveDfs(i, reachabilityMatrix, adjacentNodes);
}
...
return 0;
}
...
Question
But how to do the same without using recursion? I want to avoid a situation in which potentially I have 50000
nested calls.
Aucun commentaire:
Enregistrer un commentaire