Cod sursa(job #1163741)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 1 aprilie 2014 16:43:38
Problema Sate Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("graf.in");
ofstream g("graf.out");
 int n,m,ni,nf,dp[7505],was[7505],niv[7505],numniv[7505],sol[7505],nsol;

 vector <int> v[7505];
 queue <int> q;
 void BFS()
  { int i,nod;
      while(!q.empty())
      { nod=q.front(); q.pop();
         for(i=0;i<v[nod].size();i++)
           if (!dp[v[nod][i]])
            { dp[v[nod][i]]=dp[nod]+1;
              q.push(v[nod][i]);
            }
      }
  }

 void AntiBFS()
  { int i,nod;
      while(!q.empty())
      { nod=q.front(); q.pop();
         niv[dp[nod]]++; numniv[dp[nod]]=nod;
         for(i=0;i<v[nod].size();i++)
           if (!was[v[nod][i]] && dp[v[nod][i]]==dp[nod]-1)
            { was[v[nod][i]]=1;

              q.push(v[nod][i]);
            }
      }
  }

int main()
{ int i,x,y;
    f>>n>>m>>ni>>nf;

   for(i=1;i<=m;i++)
    { f>>x>>y;
       v[x].push_back(y);
       v[y].push_back(x);
    }

     q.push(ni); dp[ni]=1;

      BFS();

     q.push(nf); was[nf]=1;

      AntiBFS();

    for(i=1;i<=dp[nf];i++)
     if (niv[i]==1) {nsol++; sol[nsol]=numniv[i];}

     sort(sol+1,sol+nsol+1);

       g<<nsol<<"\n";
     for(i=1;i<=nsol;i++)
       g<<sol[i]<<" ";

    return 0;
}