STANAANDREY

bfs clasa

Jan 19th, 2021
612
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. using namespace std;
  3. #define NMAX 30
  4. bool adjm[NMAX][NMAX], vis[NMAX];
  5. int n, m, start;
  6. int q[NMAX], first, last, st[NMAX], top;
  7.  
  8. void read() {
  9.     cin >> n >> m >> start;
  10.     for (int i = 0; i < m; i++) {
  11.         int a, b;
  12.         cin >> a >> b;
  13.         adjm[a][b] = adjm[b][a] = true;
  14.     }
  15. }
  16.  
  17. void bfs() {
  18.     st[++top] = q[last++] = start;
  19.     vis[start] = true;
  20.     while (last != first) {
  21.         int p = q[first++];
  22.         for (int j = 1; j <= n; j++) {
  23.             if (adjm[p][j] && !vis[j]) {
  24.                 vis[j] = true;
  25.                 st[++top] = q[last++] = j;
  26.             }
  27.         }
  28.     }
  29. }
  30.  
  31. void display() {
  32.     for (int i = 1; i <= top; i++)
  33.         cout << st[i] << ' ';
  34. }
  35.  
  36. int main() {
  37.     read();
  38.     bfs();
  39.     display();
  40.     return 0;
  41. }
  42.  
RAW Paste Data