Pagini recente » Cod sursa (job #1244820) | Monitorul de evaluare | Cod sursa (job #2480693) | Cod sursa (job #1194154) | Cod sursa (job #2196594)
#include <fstream>
#include <list>
#include <vector>
using namespace std;
#ifndef __GRAPH__H
#define __GRAPH__H
// Structura Node este utila doar pentru implementarea cu liste de vecini
struct Node
{
std::vector<int> neighbors;
};
class Graph {
private:
std::vector<Node> nodes; // Implementare cu liste de vecini
// int **adiacency_matrix; // Implementare cu matrice de adiacenta
public:
Graph(int size)
{
nodes = vector<Node>(size);
}
~Graph()
{
}
//void add_node(int node); // Atentie: pentru implementarea cu matrice
//void remove_node(int node); // puteti ignora aceaste doua functii
void add_edge(int src, int dst)
{
nodes[src].neighbors.push_back(dst);
// nodes[dst].neighbors.push_back(src);
}
void remove_edge(int src, int dst)
{
int i;
for (i = 0; i < nodes[src].neighbors.size(); i++)
if (nodes[src].neighbors[i] == dst)
nodes[src].neighbors.erase(nodes[src].neighbors.begin() + i);
for (i = 0; i < nodes[dst].neighbors.size(); i++)
if (nodes[dst].neighbors[i] == src)
nodes[dst].neighbors.erase(nodes[dst].neighbors.begin() + i);
}
bool has_edge(int src, int dst)
{
int i;
for (i = 0; i < nodes[src].neighbors.size(); i++)
if (nodes[src].neighbors[i] == dst)
return true;
return false;
}
std::vector<int> get_neighbors(int node)
{
return nodes[node].neighbors;
}
};
#endif //__GRAPH__H
void dfs(Graph &g, int node, vector<bool> &viz, vector<int> &topsort)
{
if(viz[node])
return;
viz[node] = true;
for (int neigh : g.get_neighbors(node)) {
if(!viz[neigh]){
dfs(g, neigh, viz, topsort);
}
}
topsort.push_back(node);
}
int main()
{
int m, n, a, b;
ifstream f("sortaret.in");
ofstream o("sortaret.out");
f >> n >> m;
vector<int> topsort;
Graph g(n + 1);
vector<bool> viz(n + 1, 0);
for (int i = 0; i < m; i++)
{
f >> a >> b;
g.add_edge(b, a);
}
for (int j = 1; j <= n; j++) {
if(!viz[j]){
dfs(g, j, viz, topsort);
}
}
for(int x : topsort){
o << x << " ";
}
f.close();
o.close();
return 0;
}