Pagini recente » Cod sursa (job #1747357) | Cod sursa (job #1441681) | Cod sursa (job #2570041) | Cod sursa (job #1258909) | Cod sursa (job #2090127)
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#define DIM 50010
using namespace std;
queue <int> q[2];
int n, m;
vector <int> graph[DIM];
vector <int> sol;
int gradint[DIM];
void BFS()
{
bool gata = false;
int p = 0;
while (!gata)
{
gata = true;
while (!q[p].empty())
{
int x = q[p].front();
sol.push_back(x);
q[p].pop();
for (int i = 0; i < (int)graph[x].size(); ++i)
{
int y = graph[x][i];
/*graph[x][i] = graph[x].back();
graph[x].pop_back();*/
--gradint[y];
if (gradint[y] == 0)
{
gata = false;
q[1 - p].push(y);
}
}
}
p = 1 - p;
}
}
int main()
{
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
fin >> n >> m;
int x, y;
for (int i = 1;i <= m;++i)
{
fin >> x >> y;
graph[x].push_back(y);
++gradint[y];
}
for (int i = 1;i <= n;++i)
{
if (!graph[i].empty())
sort(graph[i].begin(), graph[i].end());
}
for (int i = 1;i <= n;++i)
{
if (gradint[i] == 0)
{
q[0].push(i);
}
}
BFS();
for (auto i : sol)
fout << i << " ";
fin.close();
fout.close();
return 0;
}