Pagini recente » Cod sursa (job #2035839) | Cod sursa (job #1033559) | Cod sursa (job #2563804) | Cod sursa (job #361297) | Cod sursa (job #1436397)
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <stack>
#include <cstdlib>
#include <iterator>
#include <queue>
#include <list>
using namespace std;
class Graph {
private:
vector<int> *adjList;
int nr_of_nodes;
list<int> topsortList;
public:
Graph(int V) {
nr_of_nodes = V;
adjList = new vector<int>[V + 2];
}
~Graph() {
delete[] adjList;
}
void addEdge(int u, int v) {
adjList[u].push_back(v);
}
//just for fun
void BFS(int root_node) {
bool *visited = new bool[nr_of_nodes + 2];
for (int i = 0; i < nr_of_nodes; ++i) {
visited[i] = false;
}
queue<int> Q;
vector<int>::iterator it;
int node;
visited[root_node] = true;
Q.push(root_node);
cout <<"\n";
while(!Q.empty()) {
node = Q.front();
Q.pop();
cout << node << " ";
for(it = adjList[node].begin(); it != adjList[node].end(); it++) {
if(visited[*it] == false) {
visited[*it] = true;
Q.push(*it);
}
}
}
}
void DFShelper(int node, bool *visited ) {
visited[node] = true;
topsortList.push_back(node);
vector<int>::iterator it;
//cout << node << " ";
for(it = adjList[node].begin(); it != adjList[node].end(); it++) {
if(visited[*it] == false) {
DFShelper(*it, visited);
}
}
}
void DFS() {
bool *visited = new bool[nr_of_nodes + 1];
for(int i = 0; i < nr_of_nodes; i++) {
visited[i] = false;
}
for(int node = 1; node <= nr_of_nodes; node++) {
if(visited[node] == false) {
DFShelper(node, visited);
}
}
delete[] visited;
}
list<int> getTopSortList() {
return this->topsortList;
}
};
int main(int argc, char const *argv[])
{
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
int N, M, x, y;
scanf("%d %d", &N, &M);
Graph g(N);
for(int i = 0; i < M; i++) {
scanf("%d %d", &x, &y);
g.addEdge(x,y);
}
g.DFS();
list<int> lst = g.getTopSortList();
list<int>::iterator it;
for(it = lst.begin(); it != lst.end(); ++it) {
cout << *it << " ";
}
//g.BFS(1);
return 0;
}