Cod sursa(job #1119566)

Utilizator Bigb21Avram Bogdan Bigb21 Data 24 februarie 2014 18:33:47
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<fstream>
#include<vector>
#include<iostream>
using namespace std;
ifstream in("graf.in");
ofstream out("graf.out");
vector <int> v[7501];
int c[9999999],n,m,f[7501],inc,fin,viz[7501],p=1,k=2;
void read ()
{  in>>n>>m>>inc>>fin;
   int a,b;
 for(int i=1; i<=m; i++)
 {  in>>a>>b;

    v[a].push_back(b);
    v[b].push_back(a);

 }

   c[1]=inc;
}
void BFS()
{
    if(p<=k)
    {
         for(int j=0; j<v[c[p]].size(); j++)
                { if(viz[v[c[p]][j]]==0 && v[c[p]][j]!=inc)
                      {viz[v[c[p]][j]]=viz[c[p]]+1;
                        c[k]=v[c[p]][j];
                         k++;
                      }

                  if(viz[v[c[p]][j]]!=0)
                    f[v[c[p]][j]]++;
                }

                p++;
                BFS();

    }
}
int main ()
{
      read();
      BFS();
        int q=2;
        for(int i=1; i<=n; i++)
              if(f[i]-1==viz[fin])
                q++;
            out<<q<<'\n';
            out<<inc<<" ";
                  for(int i=1; i<=n; i++)
                    {
                        if(i==fin)
                          out<<fin<<" ";

                    if(f[i]-1==viz[fin])
                       out<<i<<" ";
                    }



      in.close();
      out.close();

      return 0;
}