#include #include #include #include #include #include using namespace std; // Class to represent a graph class Graph { int V; // No. of vertices' list *adj; // A function used by topologicalSort void topologicalSortUtil(int v, bool visited[], stack &Stack); public: Graph(int V); // Constructor // function to add an edge to graph void addEdge(int v, int w); // prints a Topological Sort of the complete graph void topologicalSort(); }; Graph::Graph(int V) { this->V = V; adj = new list[V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Add w to v’s list. } // A recursive function used by topologicalSort void Graph::topologicalSortUtil(int v, bool visited[], stack &Stack) { // Mark the current node as visited. visited[v] = true; // Recur for all the vertices adjacent to this vertex list::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i]) topologicalSortUtil(*i, visited, Stack); // Push current vertex to stack which stores result Stack.push(v); } // The function to do Topological Sort. It uses recursive topologicalSortUtil() void Graph::topologicalSort() { stack Stack; // Mark all the vertices as not visited bool *visited = new bool[V]; for (int i = 0; i < V; i++) visited[i] = false; // Call the recursive helper function to store Topological Sort // starting from all vertices one by one for (int i = 0; i < V; i++) if (visited[i] == false) topologicalSortUtil(i, visited, Stack); // Print contents of stack while (Stack.empty() == false) { if (Stack.top() == 0){ cout << V << " "; } else{ cout << Stack.top() << " "; } Stack.pop(); } cout< > rel; freopen("lottery.in", "r", stdin); freopen("lottery.out", "w", stdout); int countN, x, y, maxInd = 0; scanf("%d", &countN); for (int ind = 0; ind < countN; ind++){ scanf("%d%d", &x, &y); maxInd = max(x, maxInd); maxInd = max(y, maxInd); pair edge; edge.first = x; edge.second = y; rel.push_back(edge); } Graph g(maxInd); for (int ind = 0; ind < countN; ind++){ g.addEdge(rel[ind].first, rel[ind].second); } g.topologicalSort(); return 0; }