Cod sursa(job #872542)

Utilizator misinozzz zzz misino Data 6 februarie 2013 10:56:40
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
ifstream f("graf.in");
ofstream g("graf.out");
int n,p,u,m,i,x,y,xa,ya,nod,mini,nr,dx[7505],dy[7505],v[7505],c[7505],viz[7505],num[7505],sol[7505];
vector<int>l[7505];
int main()
{
    f>>n>>m>>x>>y;
    for(i=1;i<=m;++i)
    {
        f>>xa>>ya;
        l[xa].push_back(ya);
        l[ya].push_back(xa);
    }
    c[1]=x;
    viz[x]=1;
    p=u=1;
    dx[x]=1;
    while(p<=u)
    {
        nod=c[p];
        ++p;
        for(vector<int>::iterator it=l[nod].begin();it!=l[nod].end();++it)
        if(!viz[*it])
        {
            viz[*it]=1;
            ++u;
            c[u]=*it;
            dx[*it]=dx[nod]+1;
        }
    }
    memset(viz,0,sizeof(viz));
    c[1]=y;
    p=u=1;
    dy[y]=1;
    viz[y]=1;
    while(p<=u)
    {
        nod=c[p];
        ++p;
        for(vector<int>::iterator it=l[nod].begin();it!=l[nod].end();++it)
        if(!viz[*it])
        {
            viz[*it]=1;
            ++u;
            c[u]=*it;
            dy[*it]=dy[nod]+1;
        }
    }
    mini=dx[y];
    for(i=1;i<=n;++i)
    if(dx[i]+dy[i]==mini+1)
    {
        num[dx[i]]++;
        v[dx[i]]=i;
    }
    for(i=1;i<=n;++i)
    if(num[i]==1)
    {
        ++nr;
        sol[v[i]]=1;
    }
    g<<nr<<'\n';
    for(i=1;i<=n;++i)
    if(sol[i])
    g<<i<<' ';
    g<<'\n';
    return 0;
}