Pagini recente » Cod sursa (job #1556778) | Cod sursa (job #719429) | Cod sursa (job #910904) | Cod sursa (job #1459908) | Cod sursa (job #1590023)
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <stack>
#include <queue>
template <class T>
class Graph{
public:
std::vector<std::vector<T>> graph;
unsigned nrNodes;
unsigned nrEdges;
std::vector<T> &operator[](unsigned node) {
return graph[node];
}
bool Create(unsigned nrNodes) {
graph.resize(nrNodes);
this->nrNodes = nrNodes;
return true;
}
bool TopologicalSort(std::vector<unsigned> &result) {
std::stack<std::pair<unsigned, unsigned>> st;
std::vector<bool> visited(graph.size());
unsigned tr;
for (tr = 0; tr<nrNodes; ++tr) {
if (!visited[tr]) {
st.push(std::make_pair(tr, 0));
visited[tr] = true;
while (st.size()) {
unsigned gr = st.top().first; // current node
unsigned &br = st.top().second; // adjacency list index
if (br < graph[gr].size()) {
if (!visited[graph[gr][br]]) {
visited[graph[gr][br]] = true;
st.push(std::make_pair(graph[gr][br], 0));
}
++br;
}
else {
st.pop();
result.push_back(gr);
}
}
}
}
std::reverse(result.begin(), result.end());
return true;
}
bool ConnectedComponents(std::vector<std::vector<unsigned>> &components) {
std::vector<unsigned> parent;
unsigned parentFrom, parentTo, index;
std::unordered_map<unsigned, unsigned> componentIndex;
for (unsigned i = 0; i<nrNodes; ++i) {
parent.push_back(i);
}
for (unsigned i = 0; i<nrNodes; ++i) {
for (unsigned j = 0; j<graph[i].size(); ++j) {
parentFrom = i;
parentTo = graph[i][j];
while (parent[parentFrom] != parentFrom) {
parentFrom = (parent[parentFrom] = parent[parent[parentFrom]]);
}
while (parent[parentTo] != parentTo) {
parentTo = (parent[parentTo] = parent[parent[parentTo]]);
}
if (parentFrom != parentTo) {
parent[parentFrom] = parentTo;
}
}
}
for (unsigned i = 0; i<nrNodes; ++i) {
parentFrom = parent[i];
while (parent[parentFrom] != parentFrom) {
parentFrom = (parent[parentFrom] = parent[parent[parentFrom]]);
}
if (!componentIndex.count(parentFrom)) {
unsigned index = componentIndex.size();
componentIndex[parentFrom] = index;
components.push_back(std::vector<unsigned>());
}
index = componentIndex[parentFrom];
components[index].push_back(i);
}
return true;
}
bool StrongComponents(std::vector<std::vector<unsigned>> &components) {
std::vector<unsigned> tsorted;
std::vector<std::vector<unsigned>> tgraph(graph.size());;
std::vector<bool> visited(graph.size());
unsigned tr, gr, br;
TopologicalSort(tsorted);
for (tr = 0; tr<graph.size(); ++tr) {
for (gr = 0; gr<graph[tr].size(); ++gr) {
tgraph[graph[tr][gr]].push_back(tr);
}
}
for (tr = 0; tr<tsorted.size(); ++tr) {
if (!visited[tsorted[tr]]) {
components.push_back(std::vector<unsigned>());
std::vector<unsigned> &component = components.back();
component.push_back(tsorted[tr]);
visited[tsorted[tr]] = true;
for (gr = 0; gr<component.size(); ++gr) {
for (br = 0; br<tgraph[component[gr]].size(); ++br) {
if (!visited[tgraph[component[gr]][br]]) {
visited[tgraph[component[gr]][br]] = true;
component.push_back(tgraph[component[gr]][br]);
}
}
}
}
}
return true;
}
};
int main(int argc, char *argv[])
{
int n, m;
Graph<int> g;
std::vector<unsigned> tsorted;
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
scanf("%d %d", &n, &m);
g.Create(n);
for (int i=0; i<m; ++i){
int x, y;
scanf("%d %d", &x, &y);
g[x-1].push_back(y-1);
}
g.TopologicalSort(tsorted);
for (int i=0; i<n; ++i){
printf("%d ", tsorted[i]+1);
}
return 0;
}