commit dc6d20748dbd175bcbf2155fd870ca53fb13098d
parent c74cdba0592be08f5338a6951bfac3b44efb363e
Author: Andrew Laack <andrew@laack.co>
Date: Mon, 24 Aug 2026 14:58:44 -0500
Topological sort + MHT
Diffstat:
2 files changed, 167 insertions(+), 0 deletions(-)
diff --git a/find-eventual-safe-states/find-eventual-safe-states.cpp b/find-eventual-safe-states/find-eventual-safe-states.cpp
@@ -0,0 +1,88 @@
+// idea here:
+ // we don't return nodes that have paths to cycles
+ // soln:
+ // topologically sort
+ // if a node references backwards in the sorted array mark it
+ // this implies a cycle
+ // iterate over the array, marking vertices that reference vertices that
+ // have been marked
+ // this would be O(n^2) time complexity becaues of the looping iteration
+ // process at the end
+ // better:
+ // just do dfs from each node
+ // if you run into a node that's been visited in the current traversal
+ // then unwind the stack, marking each node in the process
+ // if you don't run into a node that's been visited, propogate this backwards
+ // for each node:
+ // if it has been marked in some way, skip it
+ // if it hasn't been marked, perform the same dfs, stopping early
+ // once a node that has been marked is hit
+ // this would be O(V+E) time complexity
+
+class Solution {
+public:
+ vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
+
+ // directed graph with n nodes
+ // nodes from 0 -> n-1
+ // graph where graph[i] = [v_0,v_1,...,v_n] where v_{0->n} are adjacent to i
+
+ // terminal node := node with out-degree of 0
+ // safe node := every path from that node leads to a terminal node or another safe node
+
+ // return all safe nodes
+
+ vector<vector<int>> inList(graph.size());
+
+ vector<int> safeStack = {};
+ vector<int> safeOutDegree(graph.size());
+
+ // which nodes are safe?
+ // if a node has no out-edges it's safe
+ // it must be the case that any terminal node is like this
+ // so we can mark these and reverse propogate from there
+ // how do we find what points to the current node?
+ // we find these by creating a reverse lookup list
+
+ for(size_t i = 0; i < graph.size(); ++i) {
+
+ auto outList = graph[i];
+
+ for(auto edge: outList) {
+ inList[edge].push_back(i);
+ }
+
+ if(outList.size() == 0) {
+ safeStack.push_back(i);
+ }
+ }
+
+ // for each of the terminal nodes / safe nodes
+ // we do bfs, incrementing the number of safe out links for each
+ // of the nodes, appending them to the top sorted list iff
+ // # safe out links == number of out links.
+ // vector to return
+
+ vector<int> safe = {};
+
+ while(safeStack.size() > size_t(0)) {
+
+ auto current = safeStack.back();
+ safeStack.pop_back();
+ safe.push_back(current);
+
+ for(auto ref: inList[current]) {
+ safeOutDegree[ref] += 1;
+ if(safeOutDegree[ref] == graph[ref].size()) {
+ safeStack.push_back(ref);
+ }
+ }
+
+ }
+
+ sort(safe.begin(), safe.end());
+
+ return safe;
+
+ }
+};
diff --git a/minimum-height-trees/minimum-height-trees.cpp b/minimum-height-trees/minimum-height-trees.cpp
@@ -0,0 +1,79 @@
+class Solution {
+public:
+ vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
+ // tree with n nodes
+ // 0 -> n-1
+ // n-1 edges (deductively)
+ // edges[i] = [a_i, b_i] - edge from a_i -> b_i
+ // we can select any node to be the root (as is the case with trees)
+ // a minimum height tree is a tree that has the minimal height per the
+ // root selection.
+ // return a list of all mht root labels
+ // any order
+
+
+ // peeling:
+ // start at the leaf nodes
+ // perform bfs starting from the leaf nodes, peeling as we go
+ // once there are either 1 or 2 nodes left we know these are the MHTs
+
+ vector<int> leaves = {};
+
+ vector<int> edgeCounts(n);
+
+ vector<vector<int>> adjacencyList(n);
+
+ for(auto edge: edges) {
+ edgeCounts[edge[0]] += 1;
+ edgeCounts[edge[1]] += 1;
+ adjacencyList[edge[0]].push_back(edge[1]);
+ adjacencyList[edge[1]].push_back(edge[0]);
+ }
+
+ int remaining = n;
+
+ vector<int> checkList = {};
+ for(int i = 0 ; i < n ; ++i) {
+ checkList.push_back(i);
+ }
+
+ getLeaves(n, leaves, checkList, edgeCounts, adjacencyList);
+ remaining -= leaves.size();
+
+ int i = 0;
+
+ // remaining is the number that haven't been in the leaves list.
+ // once remaining == 0 we are done.
+
+ while (remaining > 0) {
+ leaves.clear();
+ getLeaves(n, leaves, checkList, edgeCounts, adjacencyList);
+ remaining -= leaves.size();
+ }
+
+ return leaves;
+ }
+private:
+ void getLeaves(int n, vector<int>& leaves, vector<int>& checkList, vector<int>& edgeCounts, vector<vector<int>>& adjacencyList) {
+ for(int vertex: checkList) {
+ if(edgeCounts[vertex] == 1 || edgeCounts[vertex] == 0) {
+ leaves.push_back(vertex);
+ // differentiate between orphan node and removed leaves
+ edgeCounts[vertex] = -1;
+ }
+ }
+
+ checkList.clear();
+
+ for(auto leaf: leaves) {
+ // cut edges at the end so we don't change tree under us
+ for(auto connected: adjacencyList[leaf]) {
+ edgeCounts[connected] -= 1;
+ if (edgeCounts[connected] == 1) {
+ checkList.push_back(connected);
+ }
+ }
+ }
+
+ }
+};
