Pagini recente » Cod sursa (job #1031266) | Cod sursa (job #524857) | Cod sursa (job #1229099) | Cod sursa (job #2644499) | Cod sursa (job #2790885)
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
class Graph {
std::vector<std::vector<int>> Ad;
int nodes; // no of nodes
int edges; // no of edges
int directed; // 1 for directed
public:
Graph(const std::vector<std::pair<int,int>> &ad, int nodes, int edges,int directed);
int getComponents();
void pathTo(int node);
std::stack<int> topSort();
private:
void DFS(int node, std::vector<int> &vis);
void BFS(int node, std::vector<int> &vis);
void topSortDFS(int node, std::vector<int> &vis, std::stack<int> &s);
};
Graph::Graph(const std::vector<std::pair<int,int>> &ad, int nodes, int edges, int directed) : nodes(nodes), edges(edges), directed(directed) {
Ad.resize(nodes+1);
for(int i = 0; i<edges; ++i){
Ad[ad[i].first].push_back(ad[i].second);
if(directed == 0)
Ad[ad[i].second].push_back(ad[i].first);
}
}
void Graph::DFS(int node, std::vector<int> &vis){
vis[node] = 1;
for(int i = 0; i<Ad[node].size(); ++i)
if(vis[Ad[node][i]] == 0){
DFS(Ad[node][i], vis);
}
}
int Graph::getComponents() {
std::vector<int> vis;
int ct = 0;
vis.resize(nodes);
std::fill(vis.begin(), vis.end(), 0);
for(int i = 1;i <= nodes; ++i)
if(vis[i] == 0){
DFS(i, vis);
ct++;
}
return ct;
}
void Graph::BFS(int node, std::vector<int> &vis){
int parent, distance;
std::queue<int> Q;
Q.push(node);
vis[node] = 0;
while(!Q.empty()){
parent = Q.front();
Q.pop();
for(int i = 0; i<Ad[parent].size(); ++i)
if(vis[Ad[parent][i]] == -1){
Q.push(Ad[parent][i]);
vis[Ad[parent][i]] = vis[parent] + 1;
}
}
}
void Graph::pathTo(int node){
std::vector<int> vis;
vis.resize(nodes+1);
std::fill(vis.begin(), vis.end(), -1);
vis[node] = 0;
BFS(node, vis);
for(int i = 1; i<= nodes; ++i)
fout << vis[i]<< " ";
}
void Graph::topSortDFS(int node, std::vector<int> &vis, std::stack<int> &s){
vis[node] = 1;
for(int i = 0; i<Ad[node].size(); ++i)
if(vis[Ad[node][i]] == 0)
topSortDFS(Ad[node][i], vis, s);
s.push(node);
}
std::stack<int> Graph::topSort(){
std::vector<int> vis;
std::stack<int> s;
vis.resize(nodes+1);
std::fill(vis.begin(), vis.end(), 0);
for(int i = 1; i<=nodes; ++i)
if(!vis[i])
topSortDFS(i, vis, s);
return s;
}
int main() {
std::vector<std::pair<int,int>> Ad;
std::stack<int> s;
int n,m,x,y;
fin >> n >> m;
for(int i = 0; i<m; ++i){
fin >> x >> y;
Ad.push_back({x,y});
}
Graph G(Ad,n ,m, 1);
s = G.topSort();
while(!s.empty()){
fout << s.top() << " ";
s.pop();
}
return 0;
}