Advertisement
fahad005

bfs.cpp

Aug 11th, 2021
770
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.31 KB | None | 0 0
  1. // Time complexity: O(v + e)
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. //
  5. #define ll long long
  6. #define ull unsigned long long
  7. #define pb push_back
  8. #define mx 100010
  9. #define mod 1000000007
  10. #define inf INT_MAX
  11. #define pi acos(-1)
  12. #define endl '\n'
  13. #define fin freopen("input", "r", stdin)
  14. #define Fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  15. //
  16. #define white 1
  17. #define black 2
  18.  
  19. ll node, edge, dis[mx], color[mx], parent[mx];
  20. vector<vector<ll>> adj(mx);
  21.  
  22. void bfs(ll startingNode) {
  23.     for (ll i = 0; i < node; i++) color[i] = white;
  24.  
  25.     parent[startingNode] = -1;
  26.     dis[startingNode] = 0;
  27.     queue <ll> q;
  28.     q.push(startingNode);
  29.  
  30.     while (!q.empty()) {
  31.         ll x = q.front();
  32.         q.pop();
  33.  
  34.         for (ll i = 0; i < adj[x].size(); i++) {
  35.             if (color[adj[x][i]] == white) {
  36.                 parent[adj[x][i]] = x;
  37.                 dis[adj[x][i]] = dis[x] + 1;
  38.                 q.push(adj[x][i]);
  39.             }
  40.         }
  41.         color[x] = black;
  42.     }
  43. }
  44. int main() {
  45.     cin >> node >> edge;
  46.  
  47.     for (ll i = 0; i < edge; i++) {
  48.         ll a, b;
  49.         cin >> a >> b;
  50.         adj[a].pb(b);
  51.         adj[b].pb(a); // undirected edge
  52.     }
  53.  
  54.     bfs(0); // single source.
  55.  
  56.     //Todo: can print traversal order, parent, label and many more...
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement