Cod sursa(job #2780130)

Utilizator alien14Razvan alien14 Data 6 octombrie 2021 09:32:03
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <list>
#include <stack>
#include<bits/stdc++.h>
using namespace std;
 
 ifstream fin("sortaret.in");
 ofstream fout("sortaret.out");

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) {
        fout << Stack.top()+1 << " ";
        Stack.pop();
    }
}
 
int main()
{
    int n,m;
    fin>>n>>m;
    int x,y;
    Graph g(n);
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        g.addEdge(x-1,y-1);
    }
    g.topologicalSort();
 
    return 0;
}