Cod sursa(job #704715)

Utilizator SegaXXXSergiu SegaXXX Data 2 martie 2012 19:49:23
Problema Party Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#include <memory.h>
using namespace std;

struct quoada {int k,nod;} q[7510];
int used[7510];
struct snod {int inf;snod *next;};
typedef snod *nod;
nod lv[7510],aux,p;

int main()
{
    int n,m,st,i,x,y,pq,uq;
    ifstream  fin("party.in");
    ofstream fout("party.out");
    fin>>n>>m>>st;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        aux=new snod;
        aux->inf=y;
        aux->next=lv[x];
        lv[x]=aux;
        aux=new snod;
        aux->inf=x;
        aux->next=lv[y];
        lv[y]=aux;
    }
    q[pq=uq=1].nod=st;
    q[1].k=0;
    used[st]=1;
    int nodc,kc;
    while(pq<=uq)
    {
        nodc=q[pq].nod;
        kc=q[pq++].k;
        for(p=lv[nodc];p;p=p->next)
            if(!used[p->inf])
                {
                    used[p->inf]=1;
                    q[++uq].k=kc+1;
                    q[uq].nod=p->inf;
                }
    }
    int dist=q[(n+2)/2].k;
    fout<<dist<<"\n";
    memset(used,0,sizeof(used));
    for(i=1;i<=n;i++)
        if(q[i].k==dist)
            used[q[i].nod]=1;
    for(i=1;i<=n;i++)
        if(used[i])fout<<i<<" ";
    fout.close();
    return 0;
}