Pagini recente » Cod sursa (job #717153) | Cod sursa (job #2440668) | Cod sursa (job #1178151) | Cod sursa (job #1606919) | Cod sursa (job #1846970)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
const int NMAX = 50001;
int n, m;
vector < vector < int > > graph(NMAX);
int gr_int[NMAX];
bool seen[NMAX];
void read()
{
int i, x, y;
fin >> n >> m;
for (i = 1; i <= m; ++ i)
{
fin >> x >> y;
graph[x].push_back(y);
++ gr_int[y];
}
}
void topological_sort()
{
int i;
bool ok;
vector < int > temp;
vector < int > :: iterator it, itt;
ok = false;
while (!ok)
{
ok = true;
for (i = 1; i <= n; ++ i)
if (!gr_int[i] && !seen[i])
{
temp.push_back(i);
seen[i] = true;
ok = false;
}
for(it = temp.begin(); it != temp.end(); ++ it)
{
fout << *it << " ";
for (itt = graph[*it].begin(); itt != graph[*it].end(); ++ itt)
{
-- gr_int[*itt];
graph[*it].erase(itt);
-- itt;
}
}
temp.erase(temp.begin(), temp.end());
}
fout << "\n";
}
int main()
{
read();
fin.close();
topological_sort();
fout.close();
return 0;
}