fork download
copy 
  1. #include <stdio.h>
  2. #include <queue>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. #undef DEBUG
  8.  
  9.  
  10. #ifdef DEBUG
  11.   #define debug(...) fprintf(stderr, __VA_ARGS__)
  12. #else
  13.   #define debug(...) do ; while(0)
  14. #endif
  15.  
  16.  
  17. #define MAX_EDGES	20 + 1 //We add one so we can start storing from vector[1] and not vector[0] for easineess
  18. #define MAX_NODES	80 + 1
  19.  
  20. #define UNVISITED	0
  21. #define VISITED		1
  22.  
  23. vector<int> 	adj[MAX_NODES + 1];
  24. queue<int> 	Q;
  25.  
  26. int target;
  27.  
  28. int bfs(int src)
  29. {
  30.   int front;
  31.   unsigned int i;
  32.  
  33.   /* We should not treat root seperately except when we push it
  34.    * if(src == target)					//If src (and this time root) is our target
  35.     return src;						//Then return it
  36.     
  37.   
  38.   for(i = 1; i <= adj[src].size();i++)	{		//While i is in bounds of the root's neighboor list
  39.       Q.push( adj[src].at(i) );				//Push root's neighboor i in the list
  40.    }
  41.   */
  42.   Q.push(src);
  43.  
  44.   while(!Q.empty())	{				//While Q is not empty
  45.  
  46.     front = Q.front();					//Store the front member to be examined
  47.     Q.pop();						//and pop it
  48.  
  49.     if(front == target)					//If the current examining member is our target
  50.       return front;					//Return it
  51.  
  52.     for(i = 1; i <= adj[front].size() - 1 && adj[front].at(0) != 0; i++)	{	//While i is in bounds of the list which containes front's neighboors
  53.       Q.push( adj[front].at(i) );			//Push the neighboor with identity i
  54.     }
  55.   }
  56.    return -1;
  57. }
  58.  
  59.  
  60. int main(void)	{
  61.  int node1, node2, edges, root, number_of_nodes = 0;
  62.  
  63.  for(int i = 0; i <= MAX_NODES; i++)
  64.     adj[i].clear();
  65.  
  66.  // Input
  67.  
  68.  printf("Enter Number of Edges in graph: ");
  69.  scanf("%d", &edges);
  70.  //debug("%d", edges);
  71.  
  72.  printf("Enter the connected notes numbers as identities. (eg. 1 2 is an edge conecting node 1 and node 2): ");
  73.  for(int i = 1; i <= edges; i++)	{
  74.  
  75.   scanf("%d %d", &node1, &node2);
  76.   adj[node1].push_back(node2);
  77.   //debug("%d %d", node1, adj[node1].at( adj[node1].size() - 1 ));
  78.  
  79.  }
  80.  
  81.  root = adj[1].at(0);
  82.  
  83.  printf("Enter Node to find: ");
  84.  
  85.  scanf("%d", &target);
  86.  
  87.  debug("%d\n", bfs(adj[1].at(0)));
  88.  printf("%s", (bfs(root) != - 1) ? "Exists" : "Does not exist");
  89.  //printf("%d\n", bfs( adj[1].at(0) )); //Start from 
  90.  
  91.  return 0;
  92. }
  93.  
Runtime error #stdin #stdout 0.02s 2864KB
comments (?)
stdin
copy 
3
1 2
2 3
2 4
7
stdout
copy 
Enter Number of Edges in graph: Enter the connected notes numbers as identities. (eg. 1 2 is an edge conecting node 1 and node 2): Enter Node to find:
https://ideone.com/GZwPP
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!