Pagini recente » Cod sursa (job #1336673) | Cod sursa (job #1750555) | Cod sursa (job #2012160) | Cod sursa (job #2183784) | Cod sursa (job #2921345)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Graph
{
public:
Graph(int vertices)
{
adj.resize(vertices + 1);
this->vertices = vertices;
}
void addEdge(int from, int to)
{
// cout << "adding " << from << "->" << to << endl;
auto &adjFrom = adj[from];
adjFrom.push_back(to);
}
vector<int> topSort()
{
// cout << "TopSort begin" << endl;
vector<int> inDegree(vertices + 1, 0);
for (auto adjIt = adj.begin(); adjIt != adj.end(); adjIt++)
{
if (adjIt == adj.begin())
{
continue;
}
for (auto el : *adjIt)
{
inDegree[el]++;
}
}
// for (int i = 0; i <= vertices; i++) {
// cout << "inDegree[" << i <
// }
queue<int> q;
for (auto it = inDegree.begin(); it != inDegree.end(); it++)
{
if (it == inDegree.begin())
{
continue;
}
if (*it == 0)
{
q.push(it - inDegree.begin());
}
}
vector<int> result;
while (!q.empty())
{
int el = q.front();
q.pop();
result.push_back(el);
for (auto neighbor : adj[el])
{
inDegree[neighbor]--;
if (inDegree[neighbor] == 0)
{
q.push(neighbor);
}
}
}
return result;
}
private:
vector<vector<int>> adj;
int vertices;
};
int main()
{
ifstream in("sortaret.in");
ofstream out("sortaret.out");
int n, m;
in >> n >> m;
Graph g(n);
int from, to;
for (int i = 0; i < m; i++)
{
in >> from >> to;
g.addEdge(from, to);
}
auto topSort = g.topSort();
for (auto el : topSort)
{
out << el << " ";
}
}