Pagini recente » Cod sursa (job #1651455) | Cod sursa (job #729784) | Cod sursa (job #2638777) | Cod sursa (job #107654) | Cod sursa (job #590572)
Cod sursa(job #590572)
#include <stdio.h>
#include <vector>
#include <list>
#include <algorithm>
struct node_t {
std::vector<int> in_edges;
std::vector<int> out_edges;
bool used;
};
node_t nodes[50000];
void find_roots(int n, std::list<int> &roots)
{
for (int i = 1; i <= n; i++)
{
if ((nodes[i].used == false) && (nodes[i].in_edges.size() == 0))
roots.push_back(i);
}
}
void sort(int n)
{
std::vector<int> order;
std::list<int> roots;
find_roots(n, roots);
while (!roots.empty()) {
int node = roots.front();
roots.pop_front();
order.push_back(node);
for (int i = 0; i < nodes[node].out_edges.size(); i++)
{
int m = nodes[node].out_edges.at(i);
for (std::vector<int>::iterator it = nodes[m].in_edges.begin();
it != nodes[m].in_edges.end(); ++it)
{
int x = *it;
if (x == node)
{
nodes[m].in_edges.erase(it);
break;
}
}
if (nodes[m].in_edges.size() == 0)
roots.push_back(m);
}
}
for (int i = 0; i < order.size(); i++)
printf("%d ", order[i]);
printf("\n");
}
int main()
{
int m, n, i;
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
scanf("%d %d", &n, &m);
for (i = 0; i < m; i++)
{
int x, y;
scanf("%d %d", &x, &y);
nodes[x].out_edges.push_back(y);
nodes[y].in_edges.push_back(x);
}
sort(n);
return 0;
}