Cod sursa(job #2430526)

Utilizator AxellApostolescu Alexandru Axell Data 15 iunie 2019 12:05:38
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 6.55 kb
#include <iostream>
#include <fstream>
#define INF 10000
#include <vector>
#include <queue>
#include <stack>

/**
 * Matrix implementation.
 */
class MatrixGraph {
private:
    std::vector<std::vector<int>> adjacency_matrix;
    int size;

public:
    // Constructor
    MatrixGraph(int size) {
        // TODO: TASK 1
        this->size = size;
        for (int i = 0 ; i < size ; ++i) {
          std::vector<int> tmp(size, INF);
            tmp[i] = 0;
          adjacency_matrix.push_back(tmp);
        }
    }

    // Destructor
    ~MatrixGraph() {}

    /**
     * Adds an edge between two existing nodes.
     *
     * @param src Source node of the edge to be added.
     * @param dst Destination node of the edge to be added.
     */
    void addEdge(int src, int dst, int cost  = 1) {
        if (hasEdge(src, dst)) {
            std::cout << "Duplicate betwen " << src + 1 << " " << dst + 1 << "\n";
            return;
        }
        // TODO: TASK 1
        if (src < 0 || src >= size || dst < 0 || dst >= size) {
          std::cout << "Problem with the nodes\n";
          return;
        }
        adjacency_matrix[src][dst] = cost;
    }

    /**
     * Adds an edge between two existing nodes, with given cost.
     *
     * @param src Source node of the edge to be added.
     * @param dst Destination node of the edge to be added.
     * @param cost The cost associated with the new edge.
     */
    void addEdgeWithCost(int src, int dst, int cost) {
        // TODO: BONUS 2
        if (src < 0 || src >= size || dst < 0 || dst >= size) {
          std::cout << "Problem with the nodes\n";
          return;
        }
        adjacency_matrix[src][dst] = cost;
    }

    /**
     * Removes an existing edge from the graph.
     *
     * @param src Source node of the edge to be removed.
     * @param dst Destination node of the edge to be removed.
     */
    void removeEdge(int src, int dst) {
        // TODO: TASK 1
        if (src < 0 || src >= size || dst < 0 || dst >= size) {
          std::cout << "Problem with the nodes\n";
          return;
        }
        adjacency_matrix[src][dst] = 0;
    }

    /**
     * Checks if there is an edge between two existing nodes.
     *
     * @param src Source node of the edge.
     * @param dst Destination node of the edge.
     * @return True if there is and edge between src and dst, False otherwise.
     */
    bool hasEdge(int src, int dst) {
        // TODO: TASK 1
        if (src < 0 || src >= size || dst < 0 || dst >= size) {
          std::cout << "Problem with the nodes\n";
          return false;
        }
        if (adjacency_matrix[src][dst] != INF) {
          return true;
        }
        return false;
    }

    /**
     * Returns the cost of the edge described by src and dst.
     *
     * @param src Source node of the edge.
     * @param dst Destination node of the edge.
     * @return Cost of the edge between src and dst.
     */
    int edgeCost(int src, int dst) {
        // TODO: BONUS 2
        if (src < 0 || src >= size || dst < 0 || dst >= size) {
          std::cout << "Problem with the nodes\n";
          return 0;
        }
        return adjacency_matrix[src][dst];
    }

    int cost(int src, int dst) {
        if (src < 0 || src >= size || dst < 0 || dst >= size) {
            std::cout << "Problem with the nodes\n";
            return 0;
        }
        return adjacency_matrix[src][dst];
    }

    /**
     * Gets the vector of neighbors associated with the given node.
     *
     * @param node Node whose neighbors will get returned.
     * @return A vector containing the neighbors of the given node.
     */
    std::vector<int> getNeighbors(int node) {
        // TODO: TASK 1
        std::vector<int> v;
        for (int i = 0 ; i < size ; ++i) {
          if (adjacency_matrix[node][i] == 1) {
            v.push_back(i);
          }
        }
        return v;
    }

    std::vector<int> BFS(int node) {
      std::vector<int> v;
      bool visited[size];
      std::queue<int> Q;

      for (int i = 0 ; i < size ; ++i) {
        visited[i] = false;
      }

      v.push_back(node);
      Q.push(node);
      visited[node] = true;

      while (!Q.empty()) {
        int tmp = Q.front();
        Q.pop();

        for (unsigned int i = 0 ; i < getNeighbors(tmp).size() ; ++i) {
          if (!visited[getNeighbors(tmp)[i]]) {
            v.push_back(getNeighbors(tmp)[i]);
            visited[getNeighbors(tmp)[i]] = true;
            Q.push(getNeighbors(tmp)[i]);
          }
        }

      }
    return v;
  }

  std::vector<int> sortareTopologica() {
    std::vector<bool> visited(size, false);
    std::vector<int> rez;
      for (int i = 0 ; i < size ; ++i) {
        if (!visited[i]) {
            std::vector<int> v;
            v = DFS(i, visited);
            for (auto elem : v) {
                rez.push_back(elem);
            }
        }
      }
    return rez;
  }

  std::vector<int> DFS(int node, std::vector<bool>& visited) {
    std::vector<int> v;
    std::stack<int> S;

    for (int i = 0 ; i < size ; ++i) {
      visited[i] = false;
    }

    S.push(node);
    visited[node] = true;

    while (!S.empty()) {
      int tmp = S.top();
      v.push_back(tmp);
      S.pop();

      for (unsigned int i = 0 ; i < getNeighbors(tmp).size() ; ++i) {
        if (!visited[getNeighbors(tmp)[i]]) {
          visited[getNeighbors(tmp)[i]] = true;
          S.push(getNeighbors(tmp)[i]);
        }
      }
    }
    return v;
  }

    /**
     * Gets the graph size.
     *
     * @return Number of nodes in the graph.
     */
    int getSize() {
        return size;
    }

    std::vector<std::vector<int> > getMatrix() {
        return adjacency_matrix;
    }

    friend std::ostream& operator <<(std::ostream& out, MatrixGraph& matrix);
};

std::ostream& operator <<(std::ostream& out, MatrixGraph& matrix) {
    int size = matrix.getSize();
    std::vector<std::vector<int> > v = matrix.getMatrix();
    for (int i = 0; i < size ; ++i) {
        for (int j = 0 ; j < size ; ++j) {
            out << v[i][j] << "\t";
        }
        out << "\n";
    }
    return out;
}

using namespace std;

int main() {
	ifstream in;
	ofstream out;
	in.open("sortaret.in");
	out.open("sortaret.out");
	if (!in || !out) {
		cout << "Opening files failed\n";
	}

	int numNodes, numEdges;

	in >> numNodes >> numEdges;

	MatrixGraph list(numNodes);
	for (int i = 0 ; i < numEdges ; ++i) {
		int a, b;
		in >> a >> b;
		list.addEdge(a - 1, b - 1);
	}

	std::vector<bool> visited(numNodes, false);
	std::vector<int> v = list.sortareTopologica();
	for (auto elem : v) {
		out << elem + 1 << " ";
	}
	out << "\n";


	in.close();
	out.close();

	return 0;
}