find-eventual-safe-states.cpp (3075B)
1 // idea here: 2 // we don't return nodes that have paths to cycles 3 // soln: 4 // topologically sort 5 // if a node references backwards in the sorted array mark it 6 // this implies a cycle 7 // iterate over the array, marking vertices that reference vertices that 8 // have been marked 9 // this would be O(n^2) time complexity becaues of the looping iteration 10 // process at the end 11 // better: 12 // just do dfs from each node 13 // if you run into a node that's been visited in the current traversal 14 // then unwind the stack, marking each node in the process 15 // if you don't run into a node that's been visited, propogate this backwards 16 // for each node: 17 // if it has been marked in some way, skip it 18 // if it hasn't been marked, perform the same dfs, stopping early 19 // once a node that has been marked is hit 20 // this would be O(V+E) time complexity 21 22 class Solution { 23 public: 24 vector<int> eventualSafeNodes(vector<vector<int>>& graph) { 25 26 // directed graph with n nodes 27 // nodes from 0 -> n-1 28 // graph where graph[i] = [v_0,v_1,...,v_n] where v_{0->n} are adjacent to i 29 30 // terminal node := node with out-degree of 0 31 // safe node := every path from that node leads to a terminal node or another safe node 32 33 // return all safe nodes 34 35 vector<vector<int>> inList(graph.size()); 36 37 vector<int> safeStack = {}; 38 vector<int> safeOutDegree(graph.size()); 39 40 // which nodes are safe? 41 // if a node has no out-edges it's safe 42 // it must be the case that any terminal node is like this 43 // so we can mark these and reverse propogate from there 44 // how do we find what points to the current node? 45 // we find these by creating a reverse lookup list 46 47 for(size_t i = 0; i < graph.size(); ++i) { 48 49 auto outList = graph[i]; 50 51 for(auto edge: outList) { 52 inList[edge].push_back(i); 53 } 54 55 if(outList.size() == 0) { 56 safeStack.push_back(i); 57 } 58 } 59 60 // for each of the terminal nodes / safe nodes 61 // we do bfs, incrementing the number of safe out links for each 62 // of the nodes, appending them to the top sorted list iff 63 // # safe out links == number of out links. 64 // vector to return 65 66 vector<int> safe = {}; 67 68 while(safeStack.size() > size_t(0)) { 69 70 auto current = safeStack.back(); 71 safeStack.pop_back(); 72 safe.push_back(current); 73 74 for(auto ref: inList[current]) { 75 safeOutDegree[ref] += 1; 76 if(safeOutDegree[ref] == graph[ref].size()) { 77 safeStack.push_back(ref); 78 } 79 } 80 81 } 82 83 sort(safe.begin(), safe.end()); 84 85 return safe; 86 87 } 88 };