Pagini recente » Cod sursa (job #1705807) | Cod sursa (job #2511282) | Cod sursa (job #1098824) | Cod sursa (job #104661) | Cod sursa (job #2664807)
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector < vector <int> > g;
int dm[1004];
struct nod
{
int info;
nod *ant, *urm;
};
void adauga(nod * & p, int x)
{
nod * p2 = p, * t = new nod;
t -> info = x;
if(p == NULL)
{
t -> urm = NULL;
t -> ant = NULL;
p = t;
}
else
{
while(p2 -> urm != NULL && dm[p2 -> info] < x)
p2 = p2 -> urm;
if(p2 -> info > x)
{
t -> ant = p2 -> ant;
t -> urm = p2;
p2 -> ant -> urm = t;
p2 -> ant = t;
}
else
{
t -> urm = NULL;
t -> ant = p2;
p2 -> urm = t;
}
}
}
void eliminare(nod * & p, int x)
{
nod * p2 = p;
if(p -> info == x)
{
if(p -> urm == NULL)
p = NULL;
else
{
p = p -> urm;
p -> ant = NULL;
}
}
else
{
while(p2 -> info != x)
p2 = p2 -> urm;
if(p2 -> urm == NULL)
{
p2 -> ant -> urm = NULL;
delete p2;
}
else
{
p2 -> ant -> urm = p2 -> urm;
p2 -> urm -> ant = p2 -> ant;
delete p2;
}
}
}
int main()
{
nod * s = NULL, * z = NULL;
int n, m, x, y, i, k;
fin >> n >> m;
g = vector < vector <int> >(n+1);
for(i = 1; i <= m; i++)
{
fin >> x >> y;
g[x].push_back(y);
dm[y]++;
}
for(i = 1; i <= n; i++)
adauga(s, i);
while(s != NULL)
{
while(dm[s -> info] == 0)
{
adauga(z, s -> info);
s = s -> urm;
}
while(z != NULL)
{
k = g[z -> info].size() - 1;
while(k >= 0)
{
dm[g[z -> info][k]]--;
k--;
}
fout << z -> info << " ";
z = z -> urm;
}
nod * s2 = s, * sa;
while(s2 != NULL)
{
if(dm[s2 -> info] == 0)
{
adauga(z, s2 -> info);
sa = s2;
s2 = s2 -> urm;
eliminare(s, sa -> info);
}
else
s2 = s2 -> urm;
}
}
while(z != NULL)
{
k = g[z -> info].size() - 1;
while(k >= 0)
{
dm[g[z -> info][k]]--;
k--;
}
fout << z -> info << " ";
z = z -> urm;
}
}