連結判定
(library/graph/connection.hpp)

• View this file on GitHub
• Last update: 2025-08-17 00:21:01+09:00
• Include: #include "library/graph/connection.hpp"

連結判定

グラフが連結かどうか判定する。

• is_connected(T adj_list) -> bool $O(n + m)$

隣接リストを渡す。

Depends on

• library/_internal/graph-base.hpp

Required by

• オイラー路 (library/graph/eulerian-walk.hpp)

Verified with

• tests/graph/eulerian-walk/libchecker-directed.test.cpp
• tests/graph/eulerian-walk/libchecker-undirected.test.cpp

Code

#pragma once

#include <vector>
using namespace std;

#include "../_internal/graph-base.hpp"

namespace asalib::graph {
  template<_internal::adjacency_list T>
  bool is_connected(const T& adj_list) {
    vector<bool> visited(adj_list.size(), false);
    vector<int> st;
    st.emplace_back(0);
    visited[0] = true;
    while (!st.empty()) {
      int v = st.back();
      st.pop_back();
      for (const auto& u : adj_list[v]) {
        if (!visited[u]) {
          visited[u] = true;
          st.emplace_back(u);
        }
      }
    }
    for (const auto v : visited) {
      if (!v) return false;
    }
    return true;
  }
}  // namespace asalib::graph

#line 2 "library/graph/connection.hpp"

#include <vector>
using namespace std;

#line 2 "library/_internal/graph-base.hpp"

#include <concepts>
#include <cstddef>
#include <ranges>
#include <utility>
using namespace std;

namespace asalib::_internal {
  // vector<vector<int>> とかの隣接リストを表す型
  template<class T>
  concept adjacency_list = requires(T t) {
    { t.size() } -> convertible_to<size_t>;
    { t[0] } -> ranges::range;
    { *ranges::begin(t[0]) } -> convertible_to<size_t>;
  };

  // 辺のリストを表す型
  // 重み付きも考慮し pair<int, int> と tuple<int, int, int> の両方を許容
  template<class T>
  concept edge_list = requires(T t) {
    { t.size() } -> convertible_to<size_t>;
    { get<0>(t[0]) } -> convertible_to<size_t>;
    { get<1>(t[0]) } -> convertible_to<size_t>;
  };
}  // namespace asalib::_internal
#line 7 "library/graph/connection.hpp"

namespace asalib::graph {
  template<_internal::adjacency_list T>
  bool is_connected(const T& adj_list) {
    vector<bool> visited(adj_list.size(), false);
    vector<int> st;
    st.emplace_back(0);
    visited[0] = true;
    while (!st.empty()) {
      int v = st.back();
      st.pop_back();
      for (const auto& u : adj_list[v]) {
        if (!visited[u]) {
          visited[u] = true;
          st.emplace_back(u);
        }
      }
    }
    for (const auto v : visited) {
      if (!v) return false;
    }
    return true;
  }
}  // namespace asalib::graph

Back to top page