#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, 
	                        vector<vector<int>> &adjList, 
							vector<bool> &visited, 
							vector<pair<int, pair<int, int>>> &timeStamps, 
							int &timer, bool &printVertices, bool &useTimeStamps){
		
		if(useTimeStamps){
			timer += 1; 
			timeStamps[src].second.first = timer;
		}
		
		visited[src] = true;
		
		for(auto node: adjList[src]){
			if(!visited[node]){
				
				dfsRecursiveHelper(node, adjList, visited, timeStamps, timer, printVertices, useTimeStamps);
				
				if(printVertices){
					cout<<"->"<<node;
				}
			}
		}
		
		if(useTimeStamps){
			timer += 1; 
			timeStamps[src].second.second = timer;
		}
	}
	
	void dfsRecursive(vector<vector<int>> &adjList, 
					  vector<pair<int, pair<int, int>>> &timeStamps, 
					  vector<bool> &visited,
					  bool &printVertices, 
					  bool &useTimeStamps){
		
		int timer = 0;
		int connectedComponents = 0;
		
		
		for(auto val: timeStamps)
			if(!visited[val.first]){
			
				if(printVertices)
					cout<<"The nodes in strongly connected component "<<++connectedComponents<<": "<<val.first;
					
				dfsRecursiveHelper(val.first, adjList, visited, timeStamps, timer, printVertices, useTimeStamps);
				
				if(printVertices)	
					cout<<"\n";
			}
	}
	
	void findStronglyConnectedComponents(){
		
		vector<bool> visited(n, false);
		vector<pair<int, pair<int, int>>> timeStamps(n);
		
		bool printVertices = false, useTimeStamps = true;
		
		for(int i = 0; i < n; ++i){
			timeStamps[i].first = i;
		}
		
		dfsRecursive(adj, timeStamps, visited, printVertices, useTimeStamps);
		
		sort(timeStamps.begin(), timeStamps.end(), 
			[](pair<int, pair<int, int>> &a, 
				pair<int, pair<int, int>> &b){ return a.second.second > b.second.second; });
		
		// for(auto val: timeStamps){
		// 	cout<<"Node-"<<val.first<<" | d: "<<val.second.first<<" | f: "<<val.second.second<<"\n";
		// }
		
		/*================ Transpose graph ===============*/
		vector<vector<int>> adjTranspose(n);
		
		for(int i=0; i < n; ++i){
			for(auto node: adj[i]){
				adjTranspose[node].push_back(i);
			}
		}
		/*================ Transpose graph ===============*/
		
		
		/*================ DFS on Transpose graph ================*/
		printVertices = true, useTimeStamps = false;
		visited = vector<bool>(n, false);
		
		dfsRecursive(adjTranspose, timeStamps, visited, printVertices, useTimeStamps);
		/*================ 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 Connected componets\n7. 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:
				g.findStronglyConnectedComponents();
				break;
			case 7:
				exit(0);
		} 
		cout<<"****************************************************\n";
	} 
 
	return 0;
}