Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- vector<int>node[10000];
- int parent[10000];
- int bfc(int source,int destination)
- {
- queue<int>q;
- int arr[10000],dis;
- q.push(source);
- arr[source] = 1;
- parent[source] = -1;
- while(!q.empty()){
- int n;
- n = q.front();
- q.pop();
- for(int i = 0 ; i < node[n].size() ; i++ ){
- if(node[n][i] == destination){dis = arr[n];parent[destination] = n;return dis;}
- if(arr[node[n][i]] == NULL ){
- arr[node[n][i]] = arr[n] + 1;
- parent[node[n][i]] = n;
- q.push(node[n][i]);
- }
- }
- }
- }
- int main()
- {
- int num_nodes,num_edges;
- cin >> num_nodes >> num_edges;
- for(int i = 0 ; i < num_edges ; i++){
- int x , y;
- cin >> x >> y;
- node[x].push_back(y);
- node[y].push_back(x);
- }
- int beg,last;
- cin >> beg >> last;
- cout << bfc(beg,last)<<endl;
- int n = last;
- while(parent[n] != -1 ){
- cout << n << " <- ";
- n = parent[n];
- }cout << beg << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement