Pagini recente » Cod sursa (job #1282570) | Cod sursa (job #844924) | Cod sursa (job #1417259) | Cod sursa (job #999843) | Cod sursa (job #2430519)
#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);
// for (auto elem : getNeighbors(src)) {
// std::cout << elem << " ";
// }
// std::cout << "\n";
// Sort and remove duplicates
std::sort(nodes[src].neighbors.begin(), nodes[src].neighbors.end());
for (unsigned int i = 0 ; i < nodes[src].neighbors.size() ; ++i) {
for (unsigned 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);
}
}
}
// for (auto elem : getNeighbors(src)) {
// std::cout << elem << " ";
// }
// std::cout << "\n";
}
/**
* 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;
}