#include <bits/stdc++.h> 
using namespace std; 
 
class Graph{ 
public: 
	int n;
	int m; 
	int maxEdges;
	bool isDirected;
	
	vector<vector<int>> adj;
	// int **adj;
 
	Graph(int nodes, bool isDiGraph) : adj(nodes){ 
		n = nodes;
		m = 0;
		isDirected = isDiGraph; 
		maxEdges = isDirected ? n*(n-1) : n*(n-1)/2;
 
		// adj = new int*[n];
		// for(int i = 0; i < n; ++i)
		//     adj[i] = new int[n];
	}
 
	void insertEdge(int u, int v){ 
 
		if(u >= n || v >=n || u < 0 || v < 0){ 
			cout<<"Either of the vertices doesn't exists in the graph.\n";
			return;
		}
 
		if(m == maxEdges){ 
			cout<<"Maximum allowed edges are already in the graph. Can't insert more.\n";
			return; 
		}
 
		adj[u].push_back(v); ++m; 
 
		if(!isDirected && u != v) 
			adj[v].push_back(u); 
	} 
 
	void deleteEdge(int u, int v){ 
 
		if(u >= n || v >=n || u < 0 || v < 0){
			cout<<"Either of the vertices doesn't exists in the graph.\n";
			return;
		}
 
		auto itr = find(adj[u].begin(), adj[u].end(), v);
		
		if(itr == adj[u].end()){ 
			cout<<"The edge doesn't exists in the graph.\n";
			return; 
		} 
 
		adj[u].erase(itr); --m;
 
		if(!isDirected && u != v){
			itr = find(adj[v].begin(), adj[v].end(), u);
			adj[v].erase(itr);
		}
	} 
 
	void displayGraph(){ 
 
		if(!m){ 
			cout<<"The graph is empty!!";
			return;
		} 
 
		cout<<"Total # edges in the graph: "<<m<<"\n";
 
		for(int i = 0; i < n; ++i){ 
			cout<<"The edges from vertex "<<i<<":";
 
			for(auto val: adj[i])  
				cout<<"->"<<val;
 
			cout<<"\n"; 
		} 
	}
	
	void dfsRecursiveHelper(int src, stack<int> &st, 
	                        vector<vector<int>> &adjList, 
							vector<bool> &visited, 
							bool &useStack,
							vector<int> &cycle){
		
		visited[src] = true;
		
		for(auto node: adjList[src]){
			if(!useStack && node == src){
				cycle.push_back(node);
			}
			else if(isSafe(node) && !visited[node]){
				
				dfsRecursiveHelper(node, st, adjList, visited, useStack, cycle);
				
				if(useStack){
					st.push(node);
				}
				else{
					cycle.push_back(node);
				}
			}
		}
	}
	
	void dfsRecursive(vector<vector<int>> &adjList, 
					  vector<bool> &visited,
					  stack<int> &st, 
					  bool &useStack){

		int connectedComponents = 0;
		
		vector<int> cycle;
		
		if(useStack){
			for(int i = 0; i < n; ++i)
				if(isSafe(i) && !visited[i]){
					
					dfsRecursiveHelper(i, st, adjList, visited, useStack, cycle);
					
					st.push(i);
				}
		}
		else{
			while(!st.empty()){
				int i = st.top();
				
				if(isSafe(i) && !visited[i]){
					
					dfsRecursiveHelper(i, st, adjList, visited, useStack, cycle);
					
					if(cycle.size() > 0){
						
						cout<<"The nodes in strongly connected component "<<++connectedComponents<<": "<<i;
						
						for(auto val: cycle)
							cout<<"->"<<val;
						cout<<"\n";
					}
					
					cycle.clear();
				}
				
				st.pop();
			}
		}
		
		if(!useStack && connectedComponents){
			cout<<"The directed graph has "<<connectedComponents<<" strongly connected components.\n";
		}
		else if(!useStack){
			cout<<"The directed graph doesn't has strongly connected components.\n";
		}
	}
	
	bool isSafe(int idx){
		return -1 < idx && idx < n;
	}
	
	void findStronglyConnectedComponents(){
		
		/*================ DFS on actual graph ================*/
		vector<bool> visited(n, false);
		stack<int> st;
		
		bool useStack = true;
		
		dfsRecursive(adj, visited, st, useStack);
		/*================ DFS on actual graph ================*/
		
		/*================ Transpose graph ===============*/
		vector<vector<int>> adjTranspose(n);
		
		for(int i=0; i < n; ++i){
			for(auto node: adj[i]){
				if(isSafe(node))
					adjTranspose[node].push_back(i);
			}
		}
		/*================ Transpose graph ===============*/
		
		
		/*================ DFS on Transpose graph ================*/
		useStack = false;
		visited = vector<bool>(n, false);
		
		dfsRecursive(adjTranspose, visited, st, useStack);
		/*================ DFS on Transpose graph ================*/
	}
	
	void dfsPath(int source){
		int connectedComponents = 0;
		
		vector<bool> visited(n, false);
		vector<int> pathFromSourcePredecessor(n, -1);
		
		dfs(visited, pathFromSourcePredecessor, source);
		
		for(int i = 0; i < n; ++i){
			if(!visited[i]){
				cout<<"----------------------------------------------------\n";
				dfs(visited, pathFromSourcePredecessor, i);
				++connectedComponents;
			}
		}
		
		cout<<"----------------------------------------------------\n";
		if(!connectedComponents){
			cout<<"The graph is connected.\n";
		}
		else{
			cout<<"The graph has "<<connectedComponents+1<<" connected components.\n";
		}
		
	}
	
	void dfs(vector<bool> &visited, vector<int> &pathFromSourcePredecessor, int source){
		stack<int> st;
		
		st.push(source);
		visited[source] = true;
		
		cout<<"DFS path from the source:";
		
		while(!st.empty()){
			int currVertex = st.top(); st.pop();
			
			cout<<(source == currVertex ? "":"->")<<currVertex;
			
			int prevVertex = currVertex;
			
			for(auto node: adj[currVertex]){
				if(!visited[node]){
					st.push(node);
					visited[node] = true;
					
					pathFromSourcePredecessor[node] = prevVertex;
					prevVertex = node;
				}
			}
			
		}
		
		cout<<"\nPath from source "<<source<<",\n";
		
		for(int i=0; i < n; ++i){
			if(i != source){
				cout<<"----------------------------------------------------\n";
				cout<<"To node-"<<i<<" is: ";
				
				int dest = i;
				stack<int> path;
				
				while(true){
					if(dest == source || dest == -1)
						break;
					
					path.push(dest);
					dest = pathFromSourcePredecessor[dest];
				}
				
				if(dest == -1){
					cout<<"\n\tNo path exits from the given source in this "
					<<(isDirected ? "directed graph.\n": "undirected graph.\n");
					
					if(!isDirected)
						cout<<"\tThe graph is disconnected.\n";
				}
				else{
					int pathLength = 0;
				
					cout<<source;
					
					while(!path.empty()){
						cout<<"->"<<path.top(); 
						path.pop();
						++pathLength;
					}
					
					cout<<"\n\tThe path length is: "<<pathLength<<"\n";
				}
			}
		}
	}
	
	void bfsPath(int source){
		int connectedComponents = 0;
		
		vector<bool> visited(n, false);
		vector<int> shortestPathFromSourcePredecessor(n, -1);
		
		bfs(visited, shortestPathFromSourcePredecessor, source);
		
		for(int i = 0; i < n; ++i){
			if(!visited[i]){
				cout<<"----------------------------------------------------\n";
				bfs(visited, shortestPathFromSourcePredecessor, i);
				++connectedComponents;
			}
		}
		
		cout<<"----------------------------------------------------\n";
		if(!connectedComponents){
			cout<<"The graph is connected.\n";
		}
		else{
			cout<<"The graph has "<<connectedComponents+1<<" connected components.\n";
		}
	}
	
	void bfs(vector<bool> &visited, vector<int> &shortestPathFromSourcePredecessor, int source){
		queue<int> qu;
		
		qu.push(source);
		visited[source] = true;
		
		cout<<"BFS path from source:";
		
		while(!qu.empty()){
			int currVertex = qu.front();
			qu.pop();
			
			for(auto node: adj[currVertex]){
				if(!visited[node]){
					qu.push(node);
					visited[node] = true;
					
					shortestPathFromSourcePredecessor[node] = currVertex;
				}
			}
			
			cout<<(source == currVertex ? "":"->")<<currVertex;
		}
		
		cout<<"\nShortest path from source "<<source<<",\n";
		
		for(int i=0; i < n; ++i){
			if(i != source){
				cout<<"----------------------------------------------------\n";
				cout<<"To node-"<<i<<" is: ";
				
				int dest = i;
				stack<int> path;
				
				while(true){
					if(dest == source || dest == -1)
						break;
					
					path.push(dest);
					dest = shortestPathFromSourcePredecessor[dest];
				}
				
				if(dest == -1){
					cout<<"\n\tNo path exits from the given source in this "
					<<(isDirected ? "directed graph.\n": "undirected graph.\n");
					
					if(!isDirected)
						cout<<"\tThe graph is disconnected.\n";
				}
				else{
					int pathLength = 0;
				
					cout<<source;
					
					while(!path.empty()){
						cout<<"->"<<path.top(); 
						path.pop();
						++pathLength;
					}
					
					cout<<"\n\tThe path length is: "<<pathLength<<"\n";
				}
				
			}
		}
	}
 
};
 
int main() { 
	int opt, isDir, src, dest; 
 
	cin>>opt;
	cout<<"Please enter # vertices in the graph: "<<opt<<"\n"; 
	cin>>isDir;
	cout<<"Is the graph directed(1/0)? "<<isDir<<"\n"; 
 
	Graph g(opt, isDir); 
 
	cout<<"Operations available on graph:\n"; 
	cout<<"1. Insert an edge\n2. Delete an edge\n3. Print graph\n"
	"4. BFS Path\n5. DFS Path\n6. Find strongly connected componets(If di-graph)\n"
	"7. Exit\n"; 
	cout<<"****************************************************\n"; 
	while(true){ 
		cin>>opt; 
		switch(opt){ 
			case 1:
				cin>>src>>dest; 
				cout<<"Enter the source and destination to insert edge,\n"
				"Source: " <<src<<" Destination: "<<dest<<"\n"; g.insertEdge(src, dest); 
				break;
			case 2:
				cin>>src>>dest;
				cout<<"Enter the source and destination to delete edge,\n"
				"Source: " <<src<<" Destination: "<<dest<<"\n"; g.deleteEdge(src, dest);
				break;
			case 3: 
				g.displayGraph();
				break;
			case 4:
				cin>>src;
				g.bfsPath(src);
				break;
			case 5:
				cin>>src;
				g.dfsPath(src);
				break;
			case 6:
				if(g.isDirected)
					g.findStronglyConnectedComponents();
				else
					cout<<"Current graph is not directed to find strongly connected components.\n"
					"Instead use BFS to get # connected components in undirected graph.\n";
				break;
			case 7:
				exit(0);
		} 
		cout<<"****************************************************\n";
	} 
 
	return 0;
}