Pagini recente » Cod sursa (job #2700930) | Cod sursa (job #1555972) | Cod sursa (job #2973269) | Cod sursa (job #2737871) | Cod sursa (job #1453731)
#include <fstream>
#include <vector>
#include <list>
using namespace std;
vector<list<int> > readit(int &n, int &m, ifstream &in)
{
int a, b;
vector<list<int> > w;
for(int i=0; i<n; i++)
w.push_back(list<int>());
for(int i=0; i<m; i++)
{
in >> a >> b;
--a;--b;
w[a].push_front(b);
}
return w;
}
//not prepared to detect non-dag graphs
void sortaret(vector<bool> &v, int &actual, vector<list<int> > &w, list<int> &sorted)
{
v[actual] = false;
if(w[actual].size())
{
for(list<int>::iterator it = w[actual].begin(); it!=w[actual].end(); ++it)
if(v[*it])
sortaret(v, *it, w, sorted);
}
sorted.push_front(actual);
}
int main()
{
int n, m;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
in >> n >> m;
vector<list<int> > w = readit(n, m, in);
vector<bool> v(n);
for(int i=0; i<n; i++)
v[i] = true;
list<int> sorted;
for(int i=0; i<n; i++)
if(v[i])
{
sortaret(v, i, w, sorted);
}
for(list<int>::iterator it = sorted.begin(); it!=sorted.end(); ++it)
out << *it+1 << " ";
in.close();
out.close();
return 0;
}