Cod sursa(job #797984)

Utilizator florin.ilieFlorin Ilie florin.ilie Data 15 octombrie 2012 13:36:35
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <cstdio>

using namespace std;

int n,m,u,ul;
struct nod{
	int x;
	nod *urm;
};

struct varf{
	int viz;
	nod *p;
	nod *u;
}*a[1000000];

int c[100000],ok[100000],sol[100000];

void adaugare_prim(int x,nod *&p,nod *&u)
{
	p=new nod;
	p->x=x;
	p->urm=NULL;
	u=p;
}

void adaugare_sf(int x,nod *&u)
{
	nod *q=new nod;
	q->x=x;
	q->urm=NULL;
	u->urm=q;
	u=q;
}

void adaugare (int x,nod *&p){
	nod *q= new nod;
	q->x=x;
	q->urm=p;
	p=q;
}
void stergere (nod *&p){
	nod *q=p->urm;
	p->x=q->x;
	p->urm=q->urm;
	delete q;
}

void adaug (int x,nod *&p,nod *&u)
{
	if(p==NULL)
		adaugare_prim(x,p,u);
	else
		adaugare_sf(x,p);
}

void citire ()
{
	freopen("sortaret.in","r",stdin);
	int x,y;
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++)
	{
		scanf("%d %d",&x,&y);
		adaug(y,a[x]->p,a[x]->u);
		ok[y]=1;
	}
	for(int i=1;i<=n;i++)
		if(ok[i]==0){
			c[u++]=i;
		}
}

int ver(int x)
{
	for(int i=1;i<=n;i++)
		for(nod *j=a[i]->p;j;j=j->urm)
			if(j->x==x)
				return 0;
	return 1;
}

void parc ()
{
	for(int i=0;i<u;i++){
		a[c[i]]->viz=1;
		sol[ul++]=c[i];
		for(nod *j=a[c[i]]->p;j;){
			stergere(j);
			int x=j->x;
			if(ver(x))
				c[u++]=x;
		}
	}
}

void afisare ()
{
	freopen("sortaret.out","w",stdout);
	for(int i=0;i<ul;i++)
		printf("%d ",sol[i]);
	printf("\n");
}

int main ()
{
	citire();
	parc();
	afisare();
	return 0;
}