library/graph/NegativeCycleFind.hpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Include: #include "library/graph/NegativeCycleFind.hpp"

Depends on

build/pch/stdc++.hpp

Verified with

test/AOJ/GRL_1_C.test.cpp

Code

// グラフ内に負閉路が存在するか
template<typename WG>
bool negative_cycle_find(const WG&g){
  using W=typename WG::weight_type;
  int n=g.n;
  std::vector<W> d(n,0);
  while(n--){
    bool update=false;
    for(const auto&e:g.edges)
      if(d[e.to]>d[e.from]+e.weight){
        d[e.to]=d[e.from]+e.weight;
        update=true;
      }
    if(!update)return false;
  }
  return true;
}

#line 1 "library/graph/NegativeCycleFind.hpp"
// グラフ内に負閉路が存在するか
template<typename WG>
bool negative_cycle_find(const WG&g){
  using W=typename WG::weight_type;
  int n=g.n;
  std::vector<W> d(n,0);
  while(n--){
    bool update=false;
    for(const auto&e:g.edges)
      if(d[e.to]>d[e.from]+e.weight){
        d[e.to]=d[e.from]+e.weight;
        update=true;
      }
    if(!update)return false;
  }
  return true;
}