gpt-4-0613· OpenAI
Arena Human Preference 55K
Write C++ code to topologically sort a graph
- User
Write C++ code to topologically sort a graph
- Assistant
Sure, here is a simple implementation of topological sorting in a directed graph using Depth-First Search (DFS) in C++:
#include <iostream> #include <list> #include <stack> using namespace std; class Graph { int V; list<int> *adj; void topologicalSortUtil(int v, bool visited[], stack<int> &Stack); public: Graph(int V); void addEdge(int v, int w); void topologicalSort(); }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); } void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack) { visited[v] = true; list<int>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i]) topologicalSortUtil(*i, visited, Stack); Stack.push(v); } void Graph::topologicalSort() { stack<int> Stack; bool *visited = new bool[V]; for (int i = 0; i < V; i++) visited[i] = false; for (int i = 0; i < V; i++) if (visited[i] == false) topologicalSortUtil(i, visited, Stack); while (Stack.empty() == false) { cout << Stack.top() << " "; Stack.pop(); } } int main() { Graph g(6); g.addEdge(5, 2); g.addEdge(5, 0); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1); cout << "Following is a Topological Sort of the given graph \n"; g.topologicalSort(); return 0; }This program will print the topological sorting of the given graph.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.