Cod sursa(job #2196594)

Utilizator AntonescuAlexandruAntonescu Alex AntonescuAlexandru Data 19 aprilie 2018 19:40:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.31 kb
#include <fstream>
#include <list>
#include <vector>

using namespace std;

#ifndef __GRAPH__H
#define __GRAPH__H


// Structura Node este utila doar pentru implementarea cu liste de vecini
struct Node
{
    std::vector<int> neighbors;
};

class Graph {
private:
    std::vector<Node> nodes; // Implementare cu liste de vecini
    // int **adiacency_matrix;  // Implementare cu matrice de adiacenta

public:
    Graph(int size)
    {
        nodes = vector<Node>(size);
    }

    ~Graph()
    {

    }

    //void add_node(int node);    // Atentie: pentru implementarea cu matrice
    //void remove_node(int node); // puteti ignora aceaste doua functii

    void add_edge(int src, int dst)
    {
        nodes[src].neighbors.push_back(dst);
     //   nodes[dst].neighbors.push_back(src);
    }
    void remove_edge(int src, int dst)
    {
        int i;
        for (i = 0; i < nodes[src].neighbors.size(); i++)
            if (nodes[src].neighbors[i] == dst)
                nodes[src].neighbors.erase(nodes[src].neighbors.begin() + i);
        for (i = 0; i < nodes[dst].neighbors.size(); i++)
            if (nodes[dst].neighbors[i] == src)
                nodes[dst].neighbors.erase(nodes[dst].neighbors.begin() + i);
    }
    bool has_edge(int src, int dst)
    {
        int i;
        for (i = 0; i < nodes[src].neighbors.size(); i++)
            if (nodes[src].neighbors[i] == dst)
                return true;
        return false;
    }

    std::vector<int> get_neighbors(int node)
    {
        return nodes[node].neighbors;
    }
};

#endif //__GRAPH__H


void dfs(Graph &g, int node, vector<bool> &viz, vector<int> &topsort)
{
    if(viz[node])
        return;

    viz[node] = true;
    for (int neigh : g.get_neighbors(node)) {
        if(!viz[neigh]){
            dfs(g, neigh, viz, topsort);
        }
    }
    topsort.push_back(node);

}

int main()
{
    int m, n, a, b;

    ifstream f("sortaret.in");
    ofstream o("sortaret.out");

    f >> n >> m;

    vector<int> topsort;

    Graph g(n + 1);
    vector<bool> viz(n + 1, 0);

    for (int i = 0; i < m; i++)
    {
        f >> a >> b;
        g.add_edge(b, a);
    }

    for (int j = 1; j <= n; j++) {
        if(!viz[j]){
            dfs(g, j, viz, topsort);
        }
    }

    for(int x : topsort){
        o << x << " ";
    }

    f.close();
    o.close();

    return 0;
}