Yam Code

New Paste Browse

#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; 
}

Paste Settings

Paste Title : [Optional]

Paste Folder : [Optional]

Syntax Highlighting : [Optional]

Paste Expiration : [Optional]

Paste Status : [Optional]

Password : [Optional]

Description: [Optional]

Tags: [Optional]

Encrypt Paste (?)

You are currently not logged in, this means you can not edit or delete anything you paste. Sign Up or Login

Paste Settings

Site Languages