#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, undirectedS> 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+IHsKICAgIGN5Y2xlX2RldGVjdG9yKGJvb2wmIGhhc19jeWNsZSkgOgogICAgICAgICAgICBfaGFzX2N5Y2xlKGhhc19jeWNsZSkgewogICAgfQoKICAgIHRlbXBsYXRlPGNsYXNzIEVkZ2UsIGNsYXNzIEdyYXBoPgogICAgdm9pZCBiYWNrX2VkZ2UoRWRnZSwgR3JhcGgmKSB7CiAgICAgICAgX2hhc19jeWNsZSA9IHRydWU7CiAgICB9CnByb3RlY3RlZDoKICAgIGJvb2wmIF9oYXNfY3ljbGU7Cn07CgppbnQgbWFpbihpbnQsIGNoYXIqW10pIHsKLy8gY3JlYXRlIGEgdHlwZWRlZiBmb3IgdGhlIEdyYXBoIHR5cGUKICAgIHR5cGVkZWYgYWRqYWNlbmN5X2xpc3Q8dmVjUywgdmVjUywgdW5kaXJlY3RlZFM+IEdyYXBoOwoKICAgIC8vIE1ha2UgY29udmVuaWVudCBsYWJlbHMgZm9yIHRoZSB2ZXJ0aWNlcwogICAgZW51bSB7CiAgICAgICAgQSwgQiwgQywgTgogICAgfTsKICAgIGNvbnN0IGludCBudW1fdmVydGljZXMgPSBOOwoKLy8gd3JpdGluZyBvdXQgdGhlIGVkZ2VzIGluIHRoZSBncmFwaAogICAgdHlwZWRlZiBzdGQ6OnBhaXI8aW50LCBpbnQ+IEVkZ2U7CiAgICBFZGdlIGVkZ2VfYXJyYXlbXSA9IHsKICAgICAgICAgICAgRWRnZShBLCBCKSAvLywgRWRnZShDLCBCKSwgRWRnZShBLCBDKQogICAgfTsKICAgIGNvbnN0IGludCBudW1fZWRnZXMgPSBzaXplb2YoZWRnZV9hcnJheSkgLyBzaXplb2YoZWRnZV9hcnJheVswXSk7CgoKLy8gZGVjbGFyZSBhIGdyYXBoIG9iamVjdAogICAgR3JhcGggZyhudW1fdmVydGljZXMpOwoKLy8gYWRkIHRoZSBlZGdlcyB0byB0aGUgZ3JhcGggb2JqZWN0CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG51bV9lZGdlczsgKytpKQogICAgICAgIGFkZF9lZGdlKGVkZ2VfYXJyYXlbaV0uZmlyc3QsIGVkZ2VfYXJyYXlbaV0uc2Vjb25kLCBnKTsKCiAgICBib29sIGhhc19jeWNsZSA9IGZhbHNlOwogICAgY3ljbGVfZGV0ZWN0b3IgdmlzKGhhc19jeWNsZSk7CiAgICBib29zdDo6ZGVwdGhfZmlyc3Rfc2VhcmNoKGcsIHZpc2l0b3IodmlzKSk7CiAgICBzdGQ6OmNlcnIgPDwgImhhc19jeWNsZTogIiA8PCBzdGQ6OmJvb2xhbHBoYSA8PCBoYXNfY3ljbGUgPDwgc3RkOjplbmRsOwogICAgcmV0dXJuIDA7Cn0=