Pagini recente » Cod sursa (job #1403192) | Cod sursa (job #644817) | Cod sursa (job #2838215) | Cod sursa (job #2407273) | Cod sursa (job #2662815)
#include <fstream>
#include <vector>
using namespace std;
vector<vector<int>> graph;
vector<int> top_sort_result;
vector<int> in_deg;
void top_sort()
{
for (const auto& ls : graph)
for (auto node : ls)
in_deg[node]++;
for (unsigned int i = 0; i < in_deg.size(); i++)
if (in_deg[i] == 0)
top_sort_result.push_back(i);
for (unsigned int i = 0; i < top_sort_result.size(); i++)
{
for (auto neighbor : graph[top_sort_result[i]])
{
in_deg[neighbor]--;
if (in_deg[neighbor] == 0)
top_sort_result.push_back(neighbor);
}
}
}
int main()
{
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
unsigned int n, m;
fin >> n >> m;
graph = vector<vector<int>>(n, vector<int>());
in_deg = vector<int>(n, 0);
for (unsigned int i = 0; i < m; i++)
{
int x, y;
fin >> x >> y;
x--;
y--;
graph[x].push_back(y);
}
fin.close();
top_sort();
if (top_sort_result.size() == n)
{
for (auto node : top_sort_result)
fout << node + 1 << " ";
}
fout.close();
return 0;
}