Cod sursa(job #2430414)

Utilizator AxellApostolescu Alexandru Axell Data 14 iunie 2019 17:58:58
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.94 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>

/**
* Node structure is useful only for the neighbors list implementation.
*/
struct Node {
  std::vector<int> neighbors;
};

/**
* Neighbors list implementation.
*/
class ListGraph {
private:
  std::vector<Node> nodes;
  int size;

public:
  // Constructor
  ListGraph(int size) {
      // TODO: TASK 1
      this->size = size;
      for (int i = 0 ; i < size ; ++i) {
          Node tmp;
          nodes.push_back(tmp);
      }
  }

  // Destructor
  ~ListGraph() {}

  /**
   * 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) {
      // TODO: TASK 1
      if (src < 0 || src >= size || dst < 0 || dst >= size) {
      	std::cout << "Wrong values for nodes\n";
      	return;
      }
      nodes[src].neighbors.push_back(dst);
      //  Sort and remove duplicates
      std::sort(nodes[src].neighbors.begin(), nodes[src].neighbors.end());
      for (int i = 0 ; i < nodes[src].neighbors.size() ; ++i) {
        for (int j = i + 1 ; j < nodes[src].neighbors.size() ; ++j) {
          if (nodes[src].neighbors[i] == nodes[src].neighbors[j]) {
            nodes[src].neighbors.erase(nodes[src].neighbors.begin() + i);
          }
        }
      }
  }

  /**
   * 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 << "Wrong values for nodes\n";
      	return;
      }
      std::vector<int>::iterator it;
      for (it = getNeighbors(src).begin() ; it != getNeighbors(src).end() ; ++it) {
      	if (*it == dst) {
      		nodes[src].neighbors.erase(it);
      	}
      }
  }

  /**
   * 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 an 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 << "Wrong values for nodes\n";
	  	return false;
	  }
	  std::vector<int>::iterator it;
	  for (it = getNeighbors(src).begin() ; it != getNeighbors(src).end() ; ++it) {
	  	if (*it == dst) {
	  		return true;
	  	}
	  }
    return false;
  }

  /**
   * 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
      if (node < 0 || node >= size) {
		  	std::cout << "Wrong values for nodes\n";
		  	return {};
		  }
      return nodes[node].neighbors;
  }

  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> topSort() {
    std::vector<bool> visited(size, false);
    std::vector<int> rez;
    for (int i = 0 ; i < size ; ++i) {
      std::vector<int> v;
      if (!visited[i]) {
        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;

  	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;
  }
};

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;

	ListGraph 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.topSort();
	for (auto elem : v) {
		out << elem + 1 << " ";
	}
	out << "\n";


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

	return 0;
}