BFSの実装

BFSは幅優先探索と言って、まあだいたいグラフが連結かどうかだったり、ある頂点から初めてその頂点には何通りの行き方があるかとか、最小で何手である頂点からある頂点まで行けるかを確かめたりするのに使います（他にもたくさん使いみちあるけど）。

実装

vector<int> bfs(int n,int m,vector<vector<int>>rotti){
  vector<int>amount(n,100000000);
  amount[0]=0;
  vector<int>stack={1};
  int iti=0,hako;
  set<int>irane;
  irane.insert(1);
  while (stack.size()>iti){
    hako=stack[iti];
    for (int i=0;i<rotti[hako-1].size();i++){
      if (irane.count(rotti[hako-1][i])>0)continue;
      if (amount[rotti[hako-1][i]-1]<amount[hako-1]+1)continue;
      stack.emplace_back(rotti[hako-1][i]);
      irane.insert(rotti[hako-1][i]);
      amount[rotti[hako-1][i]-1]=amount[hako-1]+1;
    }
    iti++;
  }
  for (int i=0;i<n;i++)if (amount[i]==100000000)amount[i]=-1;
  return amount;
}

この関数は、頂点の数N、辺の数M（なくてもいいけど）、頂点と頂点の連結関係を表した二次元配列を引数とし、頂点１からそれぞれの頂点への最短移動回数を格納した配列を戻り値とします。

もし、頂点ｘに頂点１から行けることができない場合、値は-1になって帰ってきます。

この関数を使う場合は、例えば以下のようなコードを書くことによって、頂点１からそれぞれの頂点への最短移動回数を出力させることができます。
i行目には頂点１から頂点iまでの最短移動回数が出力されます。

#include <bits/stdc++.h>
using namespace std;
vector<int> bfs(int n,int m,vector<vector<int>>rotti){
  vector<int>amount(n,100000000);
  amount[0]=0;
  vector<int>stack={1};
  int iti=0,hako;
  set<int>irane;
  irane.insert(1);
  while (stack.size()>iti){
    hako=stack[iti];
    for (int i=0;i<rotti[hako-1].size();i++){
      if (irane.count(rotti[hako-1][i])>0)continue;
      if (amount[rotti[hako-1][i]-1]<amount[hako-1]+1)continue;
      stack.emplace_back(rotti[hako-1][i]);
      irane.insert(rotti[hako-1][i]);
      amount[rotti[hako-1][i]-1]=amount[hako-1]+1;
    }
    iti++;
  }
  for (int i=0;i<n;i++)if (amount[i]==100000000)amount[i]=-1;
  return amount;
}
int main()
{
  int n,m,a,b;
  cin >> n >> m;
  vector<vector<int>>rotti(n);
  vector<int>amount;
  for (int i=0;i<m;i++){
    cin >> a >> b;
    rotti[a-1].emplace_back(b);
    rotti[b-1].emplace_back(a);
  }
  amount=bfs(n,m,rotti);
  for (int i=0;i<n;i++)cout << amount[i] << endl;
  return 0;
}