Cod sursa(job #1262565)

Utilizator vlady1997Vlad Bucur vlady1997 Data 13 noiembrie 2014 12:22:17
Problema Problema Damelor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
        #include <cstdio>
        #include <cstring>
        #include <algorithm>
        #include <vector>
        using namespace std;
        vector <int> g[7501];
        int a[7501], q[10001], sol[10001];
        bool ok[7501];
        int bfs (int x, int destinatie)
        {
            int p=1, u=1, i, y, nod;
            memset(q,0,sizeof(q)); memset(sol,0,sizeof(sol)); memset(ok,0,sizeof(ok));
            sol[x]=0; q[p]=x; ok[x]=true;
            while (p<=u)
            {
                nod=q[p];
                for (i=0; i<g[nod].size(); i++)
                {
                    if (ok[g[nod][i]]==false)
                    {
                        u++;
                        y=g[nod][i];
                        q[u]=y;
                        ok[g[nod][i]]=true;
                        sol[g[nod][i]]=sol[nod]+1;
                        if (g[nod][i]==destinatie)
                        {
                            return sol[g[nod][i]];
                        }
                    }
                }
                p++;
            }
        }
        int main()
        {
            int n, m, i, x, y, sursa, destinatie, s, nr=2;
            freopen("graf.in","r",stdin);
            freopen("graf.out","w",stdout);
            scanf("%d%d%d%d",&n,&m,&sursa,&destinatie);
            for (i=1; i<=m; i++)
            {
                scanf("%d%d",&x,&y);
                g[x].push_back(y);
                g[y].push_back(x);
            }
            a[1]=sursa; a[2]=destinatie; s=bfs(sursa,destinatie);
            for (i=1; i<=n; i++)
            {
                if (i==sursa || i==destinatie) continue;
                if (bfs(sursa,i)+bfs(i,destinatie)==s)
                {
                    a[++nr]=i;
                }
            }
            printf("%d\n",nr); sort(a+1,a+nr+1);
            for (i=1; i<=nr; i++) printf("%d ",a[i]);
            fclose(stdin);
            fclose(stdout);
            return 0;
        }