Pagini recente » Cod sursa (job #832108) | Cod sursa (job #2611492) | Cod sursa (job #1688966) | Cod sursa (job #1070777) | Cod sursa (job #784242)
Cod sursa(job #784242)
#include <iostream>
#include <fstream>
#include <list>
#include <queue>
#include <vector>
#define NMAX 50005
using namespace std;
list<int> toposort(vector<int> graph[], vector<int> deg, int n)
{
int i, node;
list<int> l;
queue<int> q;
vector<int>::iterator elem;
for (i = 1; i <= n; i++)
if (deg[i] == 0)
q.push(i);
while (!q.empty()) {
node = q.front();
q.pop();
l.push_back(node);
for(elem = graph[node].begin(); elem != graph[node].end();
elem++) {
deg[*elem]--;
if (deg[*elem] == 0)
q.push(*elem);
}
}
return l;
}
void print(fstream& g, list<int> l)
{
while(!l.empty()) {
g << l.front() << " ";
l.pop_front();
}
}
int main(void)
{
fstream f("sortaret.in", ios::in), g("sortaret.out", ios::out);
int n, m, i, val1, val2;
vector<int> deg, graph[NMAX];
list<int> l;
f >> n >> m;
deg.resize(n+1);
for (i = 1; i <= m; i++) {
f >> val1 >> val2;
graph[val1].push_back(val2);
deg[val2]++;
}
l = toposort(graph, deg, n);
print(g, l);
f.close();
g.close();
return 0;
}