competitve programming notes on graphs

graph.cpp

//dfs  - same for directed and undirected
// C++ program to print DFS traversal from 
// a given vertex in a given graph 
//time complexity -O(m+n) edges plus vertices 
#include<iostream> 
#include<list> 
using namespace std; 

// Graph class represents a directed graph 
// using adjacency list representation 
class Graph 
{ 
	int V; // No. of vertices 

	// Pointer to an array containing 
	// adjacency lists 
	list<int> *adj; 

	// A recursive function used by DFS 
	void DFSUtil(int v, bool visited[]); 
public: 
	Graph(int V); // Constructor 

	// function to add an edge to graph 
	void addEdge(int v, int w); 

	// DFS traversal of the vertices 
	// reachable from v 
	void DFS(int v); 
}; 

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

void Graph::addEdge(int v, int w) 
{ 
	adj[v].push_back(w); // Add w to v’s list. 
} 

void Graph::DFSUtil(int v, bool visited[]) 
{ 
	// Mark the current node as visited and 
	// print it 
	visited[v] = true; 
	cout << v << " "; 

	// Recur for all the vertices adjacent 
	// to this vertex 
	list<int>::iterator i; 
	for (i = adj[v].begin(); i != adj[v].end(); ++i) 
		if (!visited[*i]) 				

			DFSUtil(*i, visited); 
} 

// DFS traversal of the vertices reachable from v. 
// It uses recursive DFSUtil() 
void Graph::DFS(int v) 
{ 
	// Mark all the vertices as not visited 
	bool *visited = new bool[V]; 
	for (int i = 0; i < V; i++) 
		visited[i] = false; 

	// Call the recursive helper function 
	// to print DFS traversal 
	DFSUtil(v, visited); 
} 

// Driver code 
int main() 
{ 
	// Create a graph given in the above diagram 
	Graph g(4); 
	g.addEdge(0, 1); 
	g.addEdge(0, 2); 
	g.addEdge(1, 2); 
	g.addEdge(2, 0); 
	g.addEdge(2, 3); 
	g.addEdge(3, 3); 

	cout << "Following is Depth First Traversal"
			" (starting from vertex 2) \n"; 
	g.DFS(2); 

	return 0; 
} 






//number of connected components in graph
// C++ program to print connected components in 
// an undirected graph 
#include<iostream> 
#include <list> 
using namespace std; 

// Graph class represents a undirected graph 
// using adjacency list representation 
class Graph 
{ 
	int V; // No. of vertices 

	// Pointer to an array containing adjacency lists 
	list<int> *adj; 

	// A function used by DFS 
	void DFSUtil(int v, bool visited[]); 
public: 
	Graph(int V); // Constructor 
	void addEdge(int v, int w); 
	void connectedComponents(); 
}; 

// Method to print connected components in an 
// undirected graph 
void Graph::connectedComponents() 
{ 
	// Mark all the vertices as not visited 
	bool *visited = new bool[V]; 
	for(int v = 0; v < V; v++) 
		visited[v] = false; 

	for (int v=0; v<V; v++) 
	{ 
		if (visited[v] == false) 
		{ 
			// print all reachable vertices 
			// from v 
			DFSUtil(v, visited); 

			cout << "\n"; 
		} 
	} 
} 

void Graph::DFSUtil(int v, bool visited[]) 
{ 
	// Mark the current node as visited and print it 
	visited[v] = true; 
	cout << v << " "; 

	// Recur for all the vertices 
	// adjacent to this vertex 
	list<int>::iterator i; 
	for(i = adj[v].begin(); i != adj[v].end(); ++i) 
		if(!visited[*i]) 
			DFSUtil(*i, visited); 
} 

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

// method to add an undirected edge 
void Graph::addEdge(int v, int w) 
{ 
	adj[v].push_back(w); 
	adj[w].push_back(v); 
} 

// Drive program to test above 
int main() 
{ 
	// Create a graph given in the above diagram 
	Graph g(5); // 5 vertices numbered from 0 to 4 
	g.addEdge(1, 0); 
	g.addEdge(2, 3); 
	g.addEdge(3, 4); 

	cout << "Following are connected components \n"; 
	g.connectedComponents(); 

	return 0; 
} 





//detecting cycle in graph
// A C++ Program to detect cycle in a graph 
#include<iostream> 
#include <list> 
#include <limits.h> 

using namespace std; 

class Graph 
{ 
	int V; // No. of vertices 
	list<int> *adj; // Pointer to an array containing adjacency lists 
	bool isCyclicUtil(int v, bool visited[], bool *rs); // used by isCyclic() 
public: 
	Graph(int V); // Constructor 
	void addEdge(int v, int w); // to add an edge to graph 
	bool isCyclic(); // returns true if there is a cycle in this graph 
}; 

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

void Graph::addEdge(int v, int w) 
{ 
	adj[v].push_back(w); // Add w to v’s list. 
} 

// This function is a variation of DFSUtil() in https://www.geeksforgeeks.org/archives/18212 
bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack) 
{ 
	if(visited[v] == false) 
	{ 
		// Mark the current node as visited and part of recursion stack 
		visited[v] = true; 
		recStack[v] = true; 

		// Recur for all the vertices adjacent to this vertex 
		list<int>::iterator i; 
		for(i = adj[v].begin(); i != adj[v].end(); ++i) 
		{ 
			if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) ) 
				return true; 
			else if (recStack[*i]) 
				return true; 
		} 

	} 
	recStack[v] = false; // remove the vertex from recursion stack 
	return false; 
} 

// Returns true if the graph contains a cycle, else false. 
// This function is a variation of DFS() in https://www.geeksforgeeks.org/archives/18212 
bool Graph::isCyclic() 
{ 
	// Mark all the vertices as not visited and not part of recursion 
	// stack 
	bool *visited = new bool[V]; 
	bool *recStack = new bool[V]; 
	for(int i = 0; i < V; i++) 
	{ 
		visited[i] = false; 
		recStack[i] = false; 
	} 

	// Call the recursive helper function to detect cycle in different 
	// DFS trees 
	for(int i = 0; i < V; i++) 
		if (isCyclicUtil(i, visited, recStack)) 
			return true; 

	return false; 
} 

int main() 
{ 
	// Create a graph given in the above diagram 
	Graph g(4); 
	g.addEdge(0, 1); 
	g.addEdge(0, 2); 
	g.addEdge(1, 2); 
	g.addEdge(2, 0); 
	g.addEdge(2, 3); 
	g.addEdge(3, 3); 

	if(g.isCyclic()) 
		cout << "Graph contains cycle"; 
	else
		cout << "Graph doesn't contain cycle"; 
	return 0; 
} 







//getting diameter of tree
/*The second parameter is to store the height of tree. 
Initially, we need to pass a pointer to a location with value 
as 0. So, function should be used as follows: 

int height = 0; 
struct node *root = SomeFunctionToMakeTree(); 
int diameter = diameterOpt(root, &height); */
int diameterOpt(struct node *root, int* height) 
{ 
/* lh --> Height of left subtree 
	rh --> Height of right subtree */
int lh = 0, rh = 0; 

/* ldiameter --> diameter of left subtree 
	rdiameter --> Diameter of right subtree */
int ldiameter = 0, rdiameter = 0; 

if(root == NULL) 
{ 
	*height = 0; 
	return 0; /* diameter is also 0 */
} 

/* Get the heights of left and right subtrees in lh and rh 
	And store the returned values in ldiameter and ldiameter */
ldiameter = diameterOpt(root->left, &lh); 
rdiameter = diameterOpt(root->right, &rh); 

/* Height of current node is max of heights of left and 
	right subtrees plus 1*/
*height = max(lh, rh) + 1; 

return max(lh + rh + 1, max(ldiameter, rdiameter)); 
} 






#include <stdio.h> 
#include <stdlib.h> 

/* A binary tree node has data, pointer to left child 
and a pointer to right child */
struct node 
{ 
	int data; 
	struct node* left, *right; 
}; 

/* function to create a new node of tree and returns pointer */
struct node* newNode(int data); 

/* returns max of two integers */
int max(int a, int b); 

/* function to Compute height of a tree. */
int height(struct node* node); 

/* Function to get diameter of a binary tree */
int diameter(struct node * tree) 
{ 
/* base case where tree is empty */
if (tree == NULL) 
	return 0; 

/* get the height of left and right sub-trees */
int lheight = height(tree->left); 
int rheight = height(tree->right); 

/* get the diameter of left and right sub-trees */
int ldiameter = diameter(tree->left); 
int rdiameter = diameter(tree->right); 

/* Return max of following three 
1) Diameter of left subtree 
2) Diameter of right subtree 
3) Height of left subtree + height of right subtree + 1 */
return max(lheight + rheight + 1, max(ldiameter, rdiameter)); 
} 

/* UTILITY FUNCTIONS TO TEST diameter() FUNCTION */

/* The function Compute the "height" of a tree. Height is the 
	number f nodes along the longest path from the root node 
	down to the farthest leaf node.*/
int height(struct node* node) 
{ 
/* base case tree is empty */
if(node == NULL) 
	return 0; 

/* If tree is not empty then height = 1 + max of left 
	height and right heights */	
return 1 + max(height(node->left), height(node->right)); 
} 

/* Helper function that allocates a new node with the 
given data and NULL left and right pointers. */
struct node* newNode(int data) 
{ 
struct node* node = (struct node*) 
					malloc(sizeof(struct node)); 
node->data = data; 
node->left = NULL; 
node->right = NULL; 

return(node); 
} 

/* returns maximum of two integers */
int max(int a, int b) 
{ 
return (a >= b)? a: b; 
}	 

/* Driver program to test above functions*/
int main() 
{ 

/* Constructed binary tree is 
			1 
		/ \ 
		2	 3 
	/ \ 
	4	 5 
*/
struct node *root = newNode(1); 
root->left	 = newNode(2); 
root->right	 = newNode(3); 
root->left->left = newNode(4); 
root->left->right = newNode(5); 

printf("Diameter of the given binary tree is %d\n", diameter(root)); 

getchar(); 
return 0; 
} 





// A C++ Program to detect cycle in an undirected graph 
#include<iostream> 
#include <list> 
#include <limits.h> 
using namespace std; 

// Class for an undirected graph 
class Graph 
{ 
	int V; // No. of vertices 
	list<int> *adj; // Pointer to an array containing adjacency lists 
	bool isCyclicUtil(int v, bool visited[], int parent); 
public: 
	Graph(int V); // Constructor 
	void addEdge(int v, int w); // to add an edge to graph 
	bool isCyclic(); // returns true if there is a cycle 
}; 

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

void Graph::addEdge(int v, int w) 
{ 
	adj[v].push_back(w); // Add w to v’s list. 
	adj[w].push_back(v); // Add v to w’s list. 
} 

// A recursive function that uses visited[] and parent to detect 
// cycle in subgraph reachable from vertex v. 
bool Graph::isCyclicUtil(int v, bool visited[], int parent) 
{ 
	// Mark the current node as visited 
	visited[v] = true; 

	// Recur for all the vertices adjacent to this vertex 
	list<int>::iterator i; 
	for (i = adj[v].begin(); i != adj[v].end(); ++i) 
	{ 
		// If an adjacent is not visited, then recur for that adjacent 
		if (!visited[*i]) 
		{ 
		if (isCyclicUtil(*i, visited, v)) 
			return true; 
		} 

		// If an adjacent is visited and not parent of current vertex, 
		// then there is a cycle. 
		else if (*i != parent) 
		return true; 
	} 
	return false; 
} 

// Returns true if the graph contains a cycle, else false. 
bool Graph::isCyclic() 
{ 
	// Mark all the vertices as not visited and not part of recursion 
	// stack 
	bool *visited = new bool[V]; 
	for (int i = 0; i < V; i++) 
		visited[i] = false; 

	// Call the recursive helper function to detect cycle in different 
	// DFS trees 
	for (int u = 0; u < V; u++) 
		if (!visited[u]) // Don't recur for u if it is already visited 
		if (isCyclicUtil(u, visited, -1)) 
			return true; 

	return false; 
} 

// Driver program to test above functions 
int main() 
{ 
	Graph g1(5); 
	g1.addEdge(1, 0); 
	g1.addEdge(0, 2); 
	g1.addEdge(2, 1); 
	g1.addEdge(0, 3); 
	g1.addEdge(3, 4); 
	g1.isCyclic()? cout << "Graph contains cycle\n": 
				cout << "Graph doesn't contain cycle\n"; 

	Graph g2(3); 
	g2.addEdge(0, 1); 
	g2.addEdge(1, 2); 
	g2.isCyclic()? cout << "Graph contains cycle\n": 
				cout << "Graph doesn't contain cycle\n"; 

	return 0; 
} 






void dfs(int r){
vis[r]=1;
int entry=t;
for(auto it: v[r]){
if(!vis[it]){
t++;
dfs(it);
}}}