#include <iostream> // for std::cout
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/visitors.hpp>
using namespace boost;
struct cycle_detector: public dfs_visitor<> {
cycle_detector(bool& has_cycle) :
_has_cycle(has_cycle) {
}
template<class Edge, class Graph>
void back_edge(Edge, Graph&) {
_has_cycle = true;
}
protected:
bool& _has_cycle;
};
int main(int, char*[]) {
// create a typedef for the Graph type
typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;
// Make convenient labels for the vertices
enum {
A, B, C, N
};
const int num_vertices = N;
// writing out the edges in the graph
typedef std::pair<int, int> Edge;
Edge edge_array[] = {
Edge(A, B), Edge(C, B), Edge(A, C)
};
const int num_edges = sizeof(edge_array) / sizeof(edge_array[0]);
// declare a graph object
Graph g(num_vertices);
// add the edges to the graph object
for (int i = 0; i < num_edges; ++i)
add_edge(edge_array[i].first, edge_array[i].second, g);
bool has_cycle = false;
cycle_detector vis(has_cycle);
boost::depth_first_search(g, visitor(vis));
std::cerr << "has_cycle: " << std::boolalpha << has_cycle << std::endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPiAgICAgICAgICAgICAgICAgIC8vIGZvciBzdGQ6OmNvdXQKI2luY2x1ZGUgPGJvb3N0L2dyYXBoL2FkamFjZW5jeV9saXN0LmhwcD4KI2luY2x1ZGUgPGJvb3N0L2dyYXBoL2RlcHRoX2ZpcnN0X3NlYXJjaC5ocHA+CiNpbmNsdWRlIDxib29zdC9ncmFwaC92aXNpdG9ycy5ocHA+Cgp1c2luZyBuYW1lc3BhY2UgYm9vc3Q7CgpzdHJ1Y3QgY3ljbGVfZGV0ZWN0b3I6IHB1YmxpYyBkZnNfdmlzaXRvcjw+IHsKICAgIGN5Y2xlX2RldGVjdG9yKGJvb2wmIGhhc19jeWNsZSkgOgogICAgICAgICAgICBfaGFzX2N5Y2xlKGhhc19jeWNsZSkgewogICAgfQoKICAgIHRlbXBsYXRlPGNsYXNzIEVkZ2UsIGNsYXNzIEdyYXBoPgogICAgdm9pZCBiYWNrX2VkZ2UoRWRnZSwgR3JhcGgmKSB7CiAgICAgICAgX2hhc19jeWNsZSA9IHRydWU7CiAgICB9CnByb3RlY3RlZDoKICAgIGJvb2wmIF9oYXNfY3ljbGU7Cn07CgppbnQgbWFpbihpbnQsIGNoYXIqW10pIHsKLy8gY3JlYXRlIGEgdHlwZWRlZiBmb3IgdGhlIEdyYXBoIHR5cGUKICAgIHR5cGVkZWYgYWRqYWNlbmN5X2xpc3Q8dmVjUywgdmVjUywgYmlkaXJlY3Rpb25hbFM+IEdyYXBoOwoKICAgIC8vIE1ha2UgY29udmVuaWVudCBsYWJlbHMgZm9yIHRoZSB2ZXJ0aWNlcwogICAgZW51bSB7CiAgICAgICAgQSwgQiwgQywgTgogICAgfTsKICAgIGNvbnN0IGludCBudW1fdmVydGljZXMgPSBOOwoKLy8gd3JpdGluZyBvdXQgdGhlIGVkZ2VzIGluIHRoZSBncmFwaAogICAgdHlwZWRlZiBzdGQ6OnBhaXI8aW50LCBpbnQ+IEVkZ2U7CiAgICBFZGdlIGVkZ2VfYXJyYXlbXSA9IHsKICAgICAgICAgICAgRWRnZShBLCBCKSwgRWRnZShDLCBCKSwgRWRnZShBLCBDKQogICAgfTsKICAgIGNvbnN0IGludCBudW1fZWRnZXMgPSBzaXplb2YoZWRnZV9hcnJheSkgLyBzaXplb2YoZWRnZV9hcnJheVswXSk7CgovLyBkZWNsYXJlIGEgZ3JhcGggb2JqZWN0CiAgICBHcmFwaCBnKG51bV92ZXJ0aWNlcyk7CgovLyBhZGQgdGhlIGVkZ2VzIHRvIHRoZSBncmFwaCBvYmplY3QKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbnVtX2VkZ2VzOyArK2kpCiAgICAgICAgYWRkX2VkZ2UoZWRnZV9hcnJheVtpXS5maXJzdCwgZWRnZV9hcnJheVtpXS5zZWNvbmQsIGcpOwoKICAgIGJvb2wgaGFzX2N5Y2xlID0gZmFsc2U7CiAgICBjeWNsZV9kZXRlY3RvciB2aXMoaGFzX2N5Y2xlKTsKICAgIGJvb3N0OjpkZXB0aF9maXJzdF9zZWFyY2goZywgdmlzaXRvcih2aXMpKTsKICAgIHN0ZDo6Y2VyciA8PCAiaGFzX2N5Y2xlOiAiIDw8IHN0ZDo6Ym9vbGFscGhhIDw8IGhhc19jeWNsZSA8PCBzdGQ6OmVuZGw7CiAgICByZXR1cm4gMDsKfQ==