#include<iostream> 
#include <list> 
#include <limits.h> 
using namespace std; 


class DoThi 
{ 
	int V; 
	list<int> *adj; 
	bool coChuTrinhUtil(int v, bool danhdau[], int parent); 
public: 
	DoThi(int V); // Constructor 
	void themCanh(int v, int w); 
	bool coChuTrinh(); 
}; 

DoThi::DoThi(int V) 
{ 
	this->V = V; 
	adj = new list<int>[V]; 
} 

void DoThi::themCanh(int v, int w) 
{ 
	adj[v].push_back(w);
	adj[w].push_back(v);
} 

// Su dung ham de quy va mang danh dau de phat hien
// Chu ki duoc bat dau tu dinh v
bool DoThi::coChuTrinhUtil(int v, bool danhdau[], int parent) 
{ 
	// Danh dau node hien tai
	danhdau[v] = true; 

	list<int>::iterator i; 
	for (i = adj[v].begin(); i != adj[v].end(); ++i) 
	{ 
		// neu canh chua duoc danh dau thi no se kiem tra tu canh này 
		if (!danhdau[*i]) 
		{ 
		if (coChuTrinhUtil(*i, danhdau, v)) 
			return true; 
		} 

		// Neu dinh lien ke duoc danh dau va khong lien quan den dinh hien tai thi no la mot chu ki
		else if (*i != parent) 
		return true; 
	} 
	return false; 
} 

// Tra true neu do thi co chu trinh 
bool DoThi::coChuTrinh() 
{ 
	// Danh dau tat ca chua  
	bool *danhdau = new bool[V]; 
	for (int i = 0; i < V; i++) 
		danhdau[i] = false; 

	// Dung de quy de nhan ra chu trinh trong cay DFS
	for (int u = 0; u < V; u++) 
		if (!danhdau[u]) // Neu den u thi danh dau
		if (coChuTrinhUtil(u, danhdau, -1)) 
			return true; 

	return false; 
} 

// Driver program to test above functions 
int main() 
{ 
	DoThi g1(5); 
	g1.themCanh(1, 0); 
	g1.themCanh(0, 2); 
	g1.themCanh(2, 1); 
	g1.themCanh(0, 3); 
	g1.themCanh(3, 4);
	if (g1.coChuTrinh()){
		cout << "Do Thi G1 co chu trinh" << endl;
	} else {
		cout << "Do Thi G1 khong co chu trinh" << endl;
	}

	DoThi g2(3); 
	g2.themCanh(0, 1); 
	g2.themCanh(1, 2); 
	if (g2.coChuTrinh()){
		cout << "Do Thi G2 co chu trinh" << endl;
	} else {
		cout << "Do Thi G2 khong co chu trinh" << endl;
	}

	return 0; 
}