Pagini recente » Cod sursa (job #829196) | Cod sursa (job #2335512) | Cod sursa (job #2793013)
#include<iostream>
#include<queue>
#include<vector>
#include<fstream>
#include<queue>
using namespace std;
class Graph{
private:
int numberOfNodes = 0;
int numberOfEdges = 0;
vector<int> nodes;
vector<vector<int>> neighbours;
public:
Graph(int n);
Graph() {};
int getNumberOfNodes() {return this->numberOfNodes;};
void addDirectedEdge(int a, int b);
void addUndirectedEdge(int a, int b);
void bfs(int node);
vector<int> bfs_cost(int node);
vector<int> dfs(int node, vector<int> &visited, vector<int> &result);
};
Graph::Graph(int n){
this->numberOfNodes = n;
for(int i = 0; i <=n; i++)
this->neighbours.push_back(vector<int>());
}
void Graph::addUndirectedEdge(int a, int b){
this->neighbours[a].push_back(b);
this->neighbours[b].push_back(a);
this->numberOfEdges++;
}
void Graph::addDirectedEdge(int a, int b){
this->neighbours[a].push_back(b);
this->numberOfEdges++;
}
void Graph::bfs(int node){
vector<int> visited(this->getNumberOfNodes() + 1);
queue<int> q;
q.push(node);
visited[node] = 1;
while(!q.empty()) {
int currentNode = q.front();
cout<<currentNode<<" ";
q.pop();
for(int i: this->neighbours[currentNode]) {
if(!visited[i]) {
q.push(i);
visited[i] = 1;
}
}
}
cout<<"\n";
}
vector<int> Graph::bfs_cost(int node){
vector<int> visited(this->getNumberOfNodes() + 1);
queue<int> q;
vector<int> cost(this->getNumberOfNodes() + 1);
q.push(node);
visited[node] = 1;
while(!q.empty()) {
int currentNode = q.front();
q.pop();
for(int i: this->neighbours[currentNode]) {
if(!visited[i]) {
q.push(i);
cost[i] = cost[currentNode] + 1;
visited[i] = 1;
}
}
}
for(int i = 1; i <= this->getNumberOfNodes(); i++){
if(!visited[i])
cost[i] = -1;
}
return cost;
}
vector<int> Graph::dfs(int node, vector<int> &visited, vector<int> &result) {
visited[node] = 1;
result.push_back(node);
for(int i: this->neighbours[node])
if(!visited[i])
this->dfs(i, visited, result);
return result;
}
int main() {
int n, m, startNode;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
fin >> n >> m;
Graph graph = Graph(n);
for(int i = 1; i <= m; i ++)
{
int a, b;
fin >> a >> b;
graph.addDirectedEdge(a,b);
}
vector<int> visited;
for(int i = 1; i <= n; i ++)
visited.push_back(0);
vector<int> result;
graph.dfs(1, visited, result);
for(auto node: result)
fout<<node<<' ';
return 0;
}