Pagini recente » Cod sursa (job #426986) | Cod sursa (job #1919446) | Cod sursa (job #1118530) | Cod sursa (job #1421642) | Cod sursa (job #324816)
Cod sursa(job #324816)
#include<stdio.h>
long n,m;
typedef struct {long i,j;}muchii;
muchii q[100010];
long s[50001];
struct nod
{
nod *urm;
int info;
};
nod *t[50001];
long v[50001];
void read()
{
scanf("%ld%ld",&n,&m);
long i;
for (i=1;i<=m;i++)
scanf("%ld%ld",&q[i].j,&q[i].i);
}
long part(long st,long dr)
{
long i,j;
muchii aux,p;
i=st-1;
j=dr+1;
p=q[(st+dr)/2];
while (1)
{
do {i++;} while (q[i].i<p.i || (q[i].i==p.i && q[i].j<p.j));
do {j--;} while (q[j].i>p.i || (q[j].i==p.i && q[j].j>p.j));
if (i<j)
{
aux=q[i];
q[i]=q[j];
q[j]=aux;
}
else return j;
}
}
void quicks(long st,long dr)
{
long p;
if (st<dr)
{
p=part(st,dr);
quicks(st,p);
quicks(p+1,dr);
}
}
void InsertBegin(long a,long b)
{
nod *aux;
aux=new nod;
aux->info=b;
aux->urm=t[a];
t[a]=aux;
}
void arce()
{
long i;
for (i=1;i<=m;i++)
{
if (q[i].i!=q[i-1].i || q[i].j!=q[i-1].j)
{
InsertBegin(q[i].i,q[i].j);
v[q[i].j]++;
}
}
}
void parcurgere(int i)
{
nod *p;
for (p=t[i];p!=NULL;p=p->urm)
{
v[p->info]--;
}
}
void sortare()
{
long i,k;
k=1;
while (k)
{
k=0;
for (i=1;i<=n;i++)
{
if (v[i]==0)
{
k=1;
v[i]=-1;
s[++s[0]]=i;
parcurgere(i);
}
}
}
}
void print()
{
long i;
for (i=s[0];i>=1;i--)
printf("%ld ",s[i]);
}
int main()
{
freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
read();
quicks(1,m);
arce();
sortare();
print();
return 0;
}