Pagini recente » Cod sursa (job #1369950) | Cod sursa (job #1692632) | Cod sursa (job #1938814) | Cod sursa (job #1751284) | Cod sursa (job #2085386)
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#include <bitset>
#include <deque>
#define DIM 50010
using namespace std;
queue <int> q;
int n, m;
deque <int> graph[DIM];
bitset <DIM> seen;
vector <int> sol;
int gradint[DIM];
void BFS()
{
int x;
while (!q.empty())
{
x = q.front();
q.pop();
sol.push_back(x);
if (!graph[x].empty())
{
for (int i = 0;i < graph[x].size();++i)
--gradint[graph[x][i]];
if (seen[graph[x].front()] == false)
{
q.push(graph[x].front());
seen[graph[x].front()] = true;
graph[x].pop_front();
}
}
}
}
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);
}
for (int i = 1;i <= n;++i)
{
if (!graph[i].empty())
sort(graph[i].begin(), graph[i].end());
for (int j = 0;j < (int)graph[i].size();++j)
++gradint[graph[i][j]];
}
bool ok = true;
while (ok)
{
ok = false;
for (int i = 1;i <= n;++i)
if (gradint[i] == 0 && !seen[i])
{
seen[i] = true;
q.push(i);
ok = true;
}
if (ok)
BFS();
}
for (auto i : sol)
fout << i << " ";
fin.close();
fout.close();
return 0;
}