Pagini recente » Cod sursa (job #665524) | Cod sursa (job #1086521) | Cod sursa (job #1908187) | Cod sursa (job #3137329) | Cod sursa (job #784241)
Cod sursa(job #784241)
#include <iostream>
#include <fstream>
#include <list>
#include <queue>
#include <vector>
#define NMAX 50005
using namespace std;
list<int> toposort(vector<int> graph[], int n, vector<int> deg)
{
list<int> l;
queue<int> q;
int i, node;
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);
vector<int>::iterator elem;
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, n, deg);
print(g, l);
f.close();
g.close();
return 0;
}