> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/ecs122a-algorithm-design-lecture-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/ecs122a-algorithm-design-lecture-notes/basic_graph_algorithms/topological_sorting/implementation.md).

# Implementation 1

**Implementation**

```cpp
void erase(Node &n, Graph &g)
{
    if (g.graph.find(n) == g.graph.end()) { 
        cout << "Node does not exist" << endl; return; 
    }
    g.graph.erase(n);

    for (auto &i : g.graph) {
        if (i.second.find(n) != i.second.end()) {
            i.second.erase(n);
        }
    }
}

vector<string> top_ordering(Graph g)
{
    vector<string> t_order;
    t_order.reserve(g.graph.size());
    bool stop = false;
    while (!stop) {
        stop = true;
        for (auto i : g.graph) {
            if (i.second.empty()) {
                stop = false;
                t_order.push_back(i.first.id);
                erase(const_cast<Node&>(i.first), g);
                break;
            }
        }
    }

    if (!g.graph.empty()) {
        cout << "No topological ordering exists" << endl;
        return vector<string>();
    }
    else return t_order;
}
```

**A Few Remarks/Thoughts**

* I initially passed not my reference because I didn't want to mess with graph internally.
* Can be used to validate if a graph as a cycle, although this will be slow. Time complexity for this is:$$(O(|V|) + O(|V|))^2$$