DFSの実装

DFSは、ある頂点が他の頂点と連結してるかどうかを確認するアルゴリズムです（頂点１からスタートした場合、それぞれの頂点が頂点１と連結かどうか確認できる）。

BFSの下位互換でしかないので、めったに使わないです。

rotti-coder.hatenablog.com

まあ、たまにDFSの考え方を使って理解しやすくなるアルゴリズムだったりはあるけど（lowlinkとか？）

rotti-coder.hatenablog.com

実装

vector<int> dfs(int n,int m,vector<vector<int>>rotti){
  vector<int>stack{1};
  vector<int>num(n,0);
  int check=0,hako;
  num[0]=1;
  while (stack.size()>0){
    hako=stack[stack.size()-1];
    check=0;
    for (int i=0;i<rotti[hako-1].size();i++){
      if (num[rotti[hako-1][i]-1]==1)continue;
      num[rotti[hako-1][i]-1]=1;
      check=1;
      stack.emplace_back(rotti[hako-1][i]);
    }
    if (check==0)stack.pop_back();
  }
  return num;
}

この関数は頂点の数N、辺の数M（いらない）、連結関係を格納した二次元配列を引数とし、１からDFSを初めます。
それぞれの頂点が１と連結してるかどうかを配列（num）に格納し、連結の場合値は１、非連結の場合は0になっています。

例えば、以下のようなコードでそれぞれの頂点が頂点１と連結かどうかを出力することができます。

#include <bits/stdc++.h>
using namespace std;
vector<int> dfs(int n,int m,vector<vector<int>>rotti){
  vector<int>stack{1};
  vector<int>num(n,0);
  int check=0,hako;
  num[0]=1;
  while (stack.size()>0){
    hako=stack[stack.size()-1];
    check=0;
    for (int i=0;i<rotti[hako-1].size();i++){
      if (num[rotti[hako-1][i]-1]==1)continue;
      num[rotti[hako-1][i]-1]=1;
      check=1;
      stack.emplace_back(rotti[hako-1][i]);
    }
    if (check==0)stack.pop_back();
  }
  return num;
}

int main()
{
  int n,m,a,b,hako;
  cin >> n >> m;
  vector<vector<int>>rotti(n);
  vector<int>num;
  for (int i=0;i<m;i++){
    cin >> a >> b;
    rotti[a-1].emplace_back(b);
    rotti[b-1].emplace_back(a);
  }
  num=dfs(n,m,rotti);
  for (int i=0;i<n;i++){
    if (num[i]==1)cout << "Yes" << endl;
    else cout << "No" << endl;
  }
  return 0;
}