Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int bfs(int,int);
- vector<int>adj[100];
- int node,edge,i,j;
- int vis[100];
- int p[100];
- int main()
- {
- scanf("%d %d",&node,&edge);
- int node1,node2;
- memset(adj,'-1',100);
- for(i=0;i<edge;i++){
- scanf("%d %d",&node1,&node2);
- adj[node1].push_back(node2);
- adj[node2].push_back(node1);
- }
- int start,end;
- scanf("%d %d",&start,&end);
- bfs(start,end);
- }
- int bfs(int start,int end)
- {
- for(i=0;i<node;i++){
- vis[i]=0;
- }
- queue<int> q;
- q.push(start);
- vis[start]=1;
- while(!q.empty())
- {
- int u=q.front();
- q.pop();
- vis[u]=1;
- for(i=0;i<adj[u].size();i++){
- if(vis[adj[u][i]] == 0){
- int v=adj[u][i];
- vis[v]=1;
- p[v]=u;
- q.push(v);
- }
- }
- }
- if(vis[end]==0){
- return 0;
- }
- else{
- printf("Possible\n");
- vector<int> path;
- path.push_back(end);
- int x=end;
- while(x!=start)
- {
- x=p[x];
- path.push_back(x);
- }
- reverse(path.begin(),path.end());
- for(i=0;i<path.size();i++){
- cout<<path[i]<<" ";
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement