Adt lab/adjlist and bfs

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
This is part of adt lab
#include <iostream>
#include <vector>
#include <list>

using namespace std;

#define MAX_N 100000

int n,m;
vector<int> adj[MAX_N];
int deg[MAX_N];
int levels[MAX_N];

void read_input()
{
  cin >> n >> m;
  for(int i=0; i<n; i++) {
    deg[i] = 0;
  }
  for(int i=0; i<m; i++) {
    int u,v;
    cin >> u >> v;

    adj[u].push_back(v);
    adj[v].push_back(u);

    deg[u]++;
    deg[v]++;
  }
}

void find_levels(int s)
{
  list<int> next_level;
  for(int u=0; u<n; u++) {
    levels[u] = -1;
  }
  next_level.push_back(s);
  levels[s] = 0;
  
  while(! next_level.empty()) {
    list<int> current_level = next_level;
    next_level.clear();

    for(list<int>::iterator i = current_level.begin();
        i != current_level.end(); i++) {
      int u = *i;
      
      for(vector<int>::iterator j = adj[u].begin();
          j != adj[u].end(); j++) {
        int v = *j;

        if(levels[v] == -1) {
          levels[v] = levels[u] + 1;
          next_level.push_back(v);
        }
      }
    }
  }
}

main()
{
  read_input();
  find_levels(0);
  cout << levels[n-1] << endl;
}