Pagini recente » Cod sursa (job #1560585) | Rating horos grisa (horosgrisa) | Cod sursa (job #1439390) | Cod sursa (job #1535501) | Cod sursa (job #2430602)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
struct Node {
std::vector<int> neigh;
};
class ListGraph {
private:
int size;
std::vector<Node> nodes;
public:
explicit ListGraph(int size) {
this->size = size;
for (int i = 0 ; i < size ; ++i) {
Node tmp;
nodes.push_back(tmp);
}
}
~ListGraph() {
}
void addEdge(int src, int dst) {
if (src < 0 || src >= size || dst < 0 || dst >= size) {
std::cout << "Problem with nodes\n";
return;
}
if (hasEdge(src, dst)) {
return;
}
nodes[src].neigh.push_back(dst);
}
bool hasEdge(int src, int dst) {
if (src < 0 || src >= size || dst < 0 || dst >= size) {
std::cout << "Problem with nodes\n";
return false;
}
std::vector<int>::iterator it;
it = std::find(nodes[src].neigh.begin(), nodes[src].neigh.end(), dst);
if (it != nodes[src].neigh.end()) {
return true;
}
return false;
}
void removeEdge(int src, int dst) {
if (src < 0 || src >= size || dst < 0 || dst >= size) {
std::cout << "Problem with nodes\n";
return;
}
for (auto it = nodes[src].neigh.begin() ; it != nodes[src].neigh.end()
; ++it) {
if (*it == dst) {
nodes[src].neigh.erase(it);
return;
}
}
}
std::vector<int> getNeighbors(int node) {
if (node < 0 || node >= size) {
std::cout << "Problem with the node\n";
return std::vector<int>();
}
return nodes[node].neigh;
}
int getSize() {
return size;
}
std::vector<int> sortareTopologica() {
std::vector<int> result;
std::vector<bool> visited(size, false);
for (int i = 0 ; i < size ; ++i) {
if (!visited[i]) {
std::vector<int> v;
v = DFS(i, visited);
for (auto elem : v) {
result.push_back(elem);
}
}
}
return result;
}
std::vector<int> DFS(int node, std::vector<bool>& visited) {
std::vector<int> result;
visited[node] = true;
result.push_back(node);
for (unsigned int i = 0 ; i < getNeighbors(node).size() ; ++i) {
if (!visited[getNeighbors(node)[i]]) {
std::vector<int> v = DFS(getNeighbors(node)[i], visited);
for (auto elem : v) {
result.push_back(elem);
}
}
}
return result;
}
};
using namespace std;
int main() {
ifstream in;
in.open("sortaret.in");
ofstream out;
out.open("sortaret.out");
if (!in || !out) {
std::cout << "Problem with opening files!\n";
return -1;
}
// Citire
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<int> v = list.sortareTopologica();
for (auto elem : v) {
out << elem + 1 << " ";
}
out << "\n";
in.close();
out.close();
return 0;
}