Skip to content
TheChatArchiveThe Chat Archive
gpt-4-0613· OpenAIHugging Face Arena Human Preference 55K

Write C++ code to topologically sort a graph

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with vicuna-7b’s answer.
  1. User

    Write C++ code to topologically sort a graph

  2. 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.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.

Identical first prompt