Cod sursa(job #402037)

Utilizator mihaimoldovanMihai Moldovan mihaimoldovan Data 23 februarie 2010 12:49:39
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include<fstream>
#include<iostream>
using namespace std;
struct nod
{
	int info;
	nod *next;
};
#define nn 14000
nod *g[nn];
int d[nn],n,m,x,y,drum[nn],r[nn];
void adauga(int a,int b)
{
	nod *t=new nod;
	t->info=b;
	t->next=g[a];
	g[a]=t;
}
void bfs()
{
	int coada[nn],v[nn],st,dr;
	st=dr=1;
	for(int i=1;i<=n;++i)
		v[i]=0;
	d[x]=1;	
	coada[1]=x;
	v[x]=1;
	while(st<=dr)
	{
		int k=coada[st];
		if(k==y)
			break;
		for(nod*p=g[k];p;p=p->next)
		{
			int kk=p->info;
			if(!v[kk])
			{
				coada[++dr]=kk;
				v[kk]=1;
				d[kk]=d[k]+1;
			}
			else if(d[k]+1<d[kk])d[kk]=d[k]+1;
		}
		++st;
	}
}
void qsort(int st,int dr)
{
	if(st<dr)
	{
		int i=st,j=dr,aux,d=0;
		while(i<=j)
		{
			if(r[i]>r[j])
			{
				aux=r[i];
				r[i]=r[j];
				r[j]=aux;
			}
			d=1-d;
			i+=d;
			j-=1-d;
		}
		qsort(st,i-1);
		qsort(i+1,dr);
	}
}
void bfs2()
{
	int coada[nn],v[nn],st,dr;
	st=dr=1;
	for(int i=1;i<=n;++i)
		v[i]=0;
	coada[1]=y;
	v[y]=1;
	drum[y]=1;
	while(st<=dr)
	{
		int k=coada[st];
		if(k==x)
			break;
		for(nod*p=g[k];p;p=p->next)
		{
			int kk=p->info;
			if(!v[kk])
			if(d[kk]==d[k]-1)
			{
				coada[++dr]=kk;
				++drum[d[kk]];
				v[kk]=1;
			}
		}
		++st;
	}
	ofstream fout("graf.out");
	m=0;
	for(int i=1;i<=st;++i)
		if(drum[d[coada[i]]]<2)
		{
			++m;
			r[m]=coada[i];	
		}
	qsort(1,m);
	fout<<m<<endl;
	for(int i=1;i<=m;++i)
		fout<<r[i]<<" ";
}
int main()
{
	int a,b;
	ifstream fin("graf.in");
	fin>>n>>m>>x>>y;
	for(;m;--m)
	{
		fin>>a>>b;
		adauga(a,b);
		adauga(b,a);
	}
	bfs();
	bfs2();
	return 0;
}