Pagini recente » Cod sursa (job #459490) | Cod sursa (job #636878) | Cod sursa (job #377027) | Cod sursa (job #2580395) | Cod sursa (job #3267633)
#include <bits/stdc++.h>
using namespace std;
// O sortare topologica.
vector<int> sortTop(int n, vector<vector<int>> graph, vector<int> gradInt)
{
queue<int> q;
vector<int> rs;
for(int i = 1; i <= n; i++)
{
if(gradInt[i] == 0)
q.push(i);
}
while(!q.empty())
{
int nd = q.front();
rs.push_back(nd);
q.pop();
for(auto it = graph[nd].begin(); it != graph[nd].end(); it++)
{
gradInt[(*it)]--;
if(gradInt[(*it)] == 0)
{
q.push((*it));
}
}
}
return rs;
}
int main()
{
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n+1);
vector<int> gradInt(n+1);
for(int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
graph[x].push_back(y);
gradInt[y]++;
}
vector<int> rs = sortTop(n, graph, gradInt);
for(auto it = rs.begin(); it != rs.end(); it++)
{
cout << (*it) << " ";
}
}