Pagini recente » Cod sursa (job #1453970) | Cod sursa (job #2621912) | Cod sursa (job #290693) | Cod sursa (job #939074) | Cod sursa (job #1053000)
#include <map>
#include <vector>
#include <iostream>
#include <fstream>
#include <queue>
int n, m;
std::map<int, std::vector<int> > graph;
std::map<int, int> ext;
std::queue<int> good;
std::vector<int> res;
void read()
{
std::ifstream in("sortaret.in");
in >> n >> m;
for (int i = 0; i < n; i++)
{
graph.insert(std::make_pair(i + 1, std::vector<int>()));
ext.insert(std::make_pair(i + 1, 0));
}
for (int i = 0; i < m; i++)
{
int x, y;
in >> x >> y;
std::pair<std::map<int, std::vector<int> >::iterator, bool> ret = graph.insert(std::make_pair(x, std::vector<int>()));
ret.first->second.push_back(y);
std::pair<std::map<int, int>::iterator, bool> ret2 = ext.insert(std::make_pair(y, 0));
ret2.first->second++;
ext.insert(std::make_pair(x, 0));
}
for (std::map<int, int>::iterator it = ext.begin(); it != ext.end(); ++it)
if (it->second == 0)
good.push(it->first);
in.close();
}
void solve()
{
while (!good.empty())
{
int k = good.front();
good.pop();
res.push_back(k);
std::map<int, std::vector<int> >::iterator it = graph.find(k);
for (std::vector<int>::iterator it2 = it->second.begin(); it2 != it->second.end(); ++it2)
{
std::map<int, int>::iterator it3 = ext.find(*it2);
it3->second--;
if (it3->second == 0)
good.push(it3->first);
}
}
}
void write()
{
std::ofstream out("sortaret.out");
for (std::vector<int>::iterator it = res.begin(); it != res.end(); ++it)
out << *it << " ";
out << std::endl;
out.close();
}
int main()
{
read();
solve();
write();
}