Pagini recente » Cod sursa (job #1635600) | Cod sursa (job #826981) | Cod sursa (job #2285829) | Cod sursa (job #2340440) | Cod sursa (job #2430526)
#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;
}