> For the complete documentation index, see [llms.txt](https://gl01.gitbook.io/gfg-editorials/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://gl01.gitbook.io/gfg-editorials/2023/06-2023-june/01-topological-sort.md).

# 01. Topological sort

The problem can be found at the following link: [Question Link](https://practice.geeksforgeeks.org/problems/topological-sort/1)

## My Approach

To solve the problem efficiently, I have implemented the topological sort algorithm using a depth-first search (DFS) approach. Here's a breakdown of the steps involved:

1. Create a stack to store the sorted elements and initialize a vector to keep track of visited nodes.
2. Implement the DFS function, which takes in the number of nodes, an adjacency list, the visited vector, and the current node as parameters.
3. Mark the current node as visited.
4. Iterate through the adjacent nodes of the current node.
5. If an adjacent node has not been visited, recursively call the DFS function on that node.
6. Once all adjacent nodes have been visited, push the current node onto the stack.
7. In the topoSort function, initialize the visited vector with zeros.
8. Iterate through all nodes and call the DFS function on any unvisited nodes.
9. Pop the elements from the stack and store them in the visited vector in reverse order.
10. Finally, return the sorted vector.

## Time and Auxiliary Space Complexity

* **Time Complexity**: `O(V + E)`, where `V` represents the number of vertices (nodes) and `E` represents the number of edges in the graph. This complexity arises from traversing all nodes and their adjacent edges during the DFS traversal.
* **Auxiliary Space Complexity**: `O(V)`, where V represents the number of vertices. This complexity is due to the usage of the stack and the visited vector, both of which grow with the number of nodes in the graph.

## Code (C++)

```cpp

class Solution
{
	public:
	stack<int> st;
	void dfs(int n, vector<int> adj[],vector<int>& vis, int node){
	    vis[node] = 1;
	    for(auto i: adj[node]){
	        if(!vis[i]){
	            dfs(n,adj,vis,i);
	        }
	    }
        st.push(node);
	}
	vector<int> topoSort(int n, vector<int> adj[]) 
	{
	    vector<int> vis(n,0);
	    for(int i = 0;i<n;++i){
	        if(!vis[i]){
	            dfs(n,adj,vis,i);
	        }
	    }
	    int i = 0;
	    while(!st.empty()){
	        vis[i++] = st.top();
	        st.pop();
	    }
	    return vis;
	}
};

```

## Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our [discussion section](https://github.com/getlost01/gfg-potd/discussions). We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a `⭐ star` to the [getlost01/gfg-potd](https://github.com/getlost01/gfg-potd) repository.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://gl01.gitbook.io/gfg-editorials/2023/06-2023-june/01-topological-sort.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.