Pagini recente » Cod sursa (job #2023904) | Cod sursa (job #1303306) | Cod sursa (job #2231845) | Cod sursa (job #297739) | Cod sursa (job #1745591)
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 50005;
vector <int> L[Nmax];
int viz[Nmax], n, sol[Nmax], p;
queue <int> q;
priority_queue <int> qq;
void Citire()
{
ifstream f("sortaret.in");
int m, i, x, y;
f >> n >> m;
for(i = 1; i <= m; i++)
{
f >> x >> y;
L[x].push_back(y);
viz[y]++;
}
f.close();
}
void BFS()
{
int cnt1, cnt2;
cnt1 = cnt2 = 0;
for(int i = 1; i <= n; i++)
if(viz[i] == 0)
q.push(i), cnt1++, sol[++p] = i;
while(!q.empty())
{
int k = q.front();
q.pop();
for(unsigned int i = 0; i < L[k].size(); i++)
{
int j = L[k][i];
viz[j]--;
if(viz[j] == 0)
{
q.push(j);
qq.push(-j);
cnt2++;
}
}
cnt1--;
if(cnt1 == 0)
{
cnt1 = cnt2;
while(!qq.empty())
{
sol[++p] = -qq.top();
qq.pop();
}
}
}
while(!qq.empty())
{
sol[++p] = -qq.top();
qq.pop();
}
}
void Afisare()
{
ofstream g("sortaret.out");
for(int i = 1; i <= n; i++)
g << sol[i] << " ";
g << "\n";
g.close();
}
int main()
{
Citire();
BFS();
Afisare();
return 0;
}