Pagini recente » Cod sursa (job #638472) | Cod sursa (job #442504) | Cod sursa (job #1493635) | Cod sursa (job #2579697) | Cod sursa (job #2786713)
#include <fstream>
#include <iostream>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
FILE *fin = fopen("sortaret.in", "r");
FILE *fout = fopen("sortaret.out", "w");
class Graph
{
private:
int cntNodes;
vector<set<int>> fromToList;
vector<set<int>> toFromList;
public:
Graph(int n)
{
cntNodes = n;
for (int i = 0; i < n; ++i)
{
fromToList.push_back(set<int>());
toFromList.push_back(set<int>());
}
}
void addEdge(int from, int to)
{
fromToList[from].insert(to);
toFromList[to].insert(from);
}
vector<int> topologicalSorting()
{
vector<int> queue;
bool visited[cntNodes];
fill(visited, visited + cntNodes, false);
for (int i = 0; i < cntNodes; ++i)
{
if (fromToList[i].empty())
{
visited[i] = true;
queue.push_back(i);
}
}
int it = 0;
while (it < queue.size())
{
int toNodeId = queue[it++];
for (int fromNodeId : toFromList[toNodeId])
{
if (!visited[fromNodeId])
{
fromToList[fromNodeId].erase(toNodeId);
if (fromToList[fromNodeId].empty())
{
visited[fromNodeId] = true;
queue.push_back(fromNodeId);
}
}
}
}
reverse(queue.begin(), queue.end());
return queue;
}
};
int n, m, a, b, s;
int main()
{
fscanf(fin, "%d %d", &n, &m);
// fin >> n >> m;
Graph g(n);
for (int i = 0; i < m; ++i)
{
fscanf(fin, "%d %d", &a, &b);
g.addEdge(a - 1, b - 1);
}
vector<int> r = g.topologicalSorting();
for (int nodeId : r)
{
fprintf(fout, "%d ", nodeId + 1);
// fout << nodeId + 1 << " ";
}
return 0;
}