Pagini recente » Cod sursa (job #3181006) | Cod sursa (job #1282243) | Cod sursa (job #2867211) | Cod sursa (job #2327881) | Cod sursa (job #1230748)
#include <fstream>
#include <queue>
#include <list>
#include <bitset>
using namespace std;
#define SIZE 100001
list<int> A[SIZE]; // Adjacency lists
bitset<SIZE> V; // Visited vector
short MP[SIZE]; // Stores the size of the minimum path from START to DESTINATION
int main()
{
ifstream ifs("bfs.in");
ofstream ofs("bfs.out");
int n, m, s;
ifs >> n >> m >> s;
for (int i = 0; i < m; ++i)
{
int x, y;
ifs >> x >> y;
A[x].push_back(y);
}
// Do BFS
queue<pair<int, int> > Q;
Q.push(make_pair(s, 0));
while (!Q.empty())
{
pair<int, int> p = Q.front();
V.set(p.first);
MP[p.first] = p.second;
list<int> adj_list = A[p.first];
for (list<int>::iterator it = adj_list.begin(); it != adj_list.end(); ++it)
if (!V.test(*it))
Q.push(make_pair(*it, p.second + 1));
}
for (int i = 1; i < s; ++i)
ofs << (MP[i] > 0 ? MP[i] : -1) << " ";
ofs << 0 << " ";
for (int i = s+1; i < n; ++i)
ofs << (MP[i] > 0 ? MP[i] : -1) << " ";
return 0;
}