fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std; 
  3.  
  4. class Graph{ 
  5. public: 
  6. 	int n;
  7. 	int m; 
  8. 	int maxEdges;
  9. 	bool isDirected;
  10.  
  11. 	vector<vector<int>> adj;
  12. 	// int **adj;
  13.  
  14. 	Graph(int nodes, bool isDiGraph) : adj(nodes){ 
  15. 		n = nodes;
  16. 		m = 0;
  17. 		isDirected = isDiGraph; 
  18. 		maxEdges = isDirected ? n*(n-1) : n*(n-1)/2;
  19.  
  20. 		// adj = new int*[n];
  21.  
  22. 		// for(int i = 0; i < n; ++i)
  23. 		//     adj[i] = new int[n];
  24. 	}
  25.  
  26. 	void insertEdge(int u, int v){ 
  27.  
  28. 		if(u >= n || v >=n || u < 0 || v < 0){ 
  29. 			cout<<"Either of the vertices doesn't exists in the graph.\n";
  30. 			return;
  31. 		}
  32.  
  33. 		if(m == maxEdges){ 
  34. 			cout<<"Maximum allowed edges are already in the graph. Can't insert more.\n";
  35. 			return; 
  36. 		}
  37.  
  38. 		adj[u].push_back(v); ++m; 
  39.  
  40. 		if(!isDirected && u != v) 
  41. 			adj[v].push_back(u); 
  42. 	} 
  43.  
  44. 	void deleteEdge(int u, int v){ 
  45.  
  46. 		if(u >= n || v >=n || u < 0 || v < 0){
  47. 			cout<<"Either of the vertices doesn't exists in the graph.\n";
  48. 			return;
  49. 		}
  50.  
  51. 		auto itr = find(adj[u].begin(), adj[u].end(), v);
  52.  
  53. 		if(itr == adj[u].end()){ 
  54. 			cout<<"The edge doesn't exists in the graph.\n";
  55. 			return; 
  56. 		} 
  57.  
  58. 		adj[u].erase(itr); --m;
  59.  
  60. 		if(!isDirected && u != v){
  61. 			itr = find(adj[v].begin(), adj[v].end(), u);
  62. 			adj[v].erase(itr);
  63. 		}
  64. 	} 
  65.  
  66. 	void displayGraph(){ 
  67.  
  68. 		if(!m){ 
  69. 			cout<<"The graph is empty!!";
  70. 			return;
  71. 		} 
  72.  
  73. 		cout<<"Total # edges in the graph: "<<m<<"\n";
  74.  
  75. 		for(int i = 0; i < n; ++i){ 
  76. 			cout<<"The edges from vertex "<<i<<":";
  77.  
  78. 			for(auto val: adj[i])  
  79. 				cout<<"->"<<val;
  80.  
  81. 			cout<<"\n"; 
  82. 		} 
  83. 	}
  84.  
  85. 	void dfsRecursiveHelper(int src, 
  86. 	                        vector<vector<int>> &adjList, 
  87. 							vector<bool> &visited, 
  88. 							vector<pair<int, pair<int, int>>> &timeStamps, 
  89. 							int &timer, bool &printVertices, bool &useTimeStamps){
  90.  
  91. 		if(useTimeStamps){
  92. 			timer += 1; 
  93. 			timeStamps[src].second.first = timer;
  94. 		}
  95.  
  96. 		visited[src] = true;
  97.  
  98. 		for(auto node: adjList[src]){
  99. 			if(!visited[node]){
  100.  
  101. 				dfsRecursiveHelper(node, adjList, visited, timeStamps, timer, printVertices, useTimeStamps);
  102.  
  103. 				if(printVertices){
  104. 					cout<<"->"<<node;
  105. 				}
  106. 			}
  107. 		}
  108.  
  109. 		if(useTimeStamps){
  110. 			timer += 1; 
  111. 			timeStamps[src].second.second = timer;
  112. 		}
  113. 	}
  114.  
  115. 	void dfsRecursive(vector<vector<int>> &adjList, 
  116. 					  vector<pair<int, pair<int, int>>> &timeStamps, 
  117. 					  vector<bool> &visited,
  118. 					  bool &printVertices, 
  119. 					  bool &useTimeStamps){
  120.  
  121. 		int timer = 0;
  122. 		int connectedComponents = 0;
  123.  
  124.  
  125. 		for(auto val: timeStamps)
  126. 			if(!visited[val.first]){
  127.  
  128. 				if(printVertices)
  129. 					cout<<"The nodes in strongly connected component "<<++connectedComponents<<": "<<val.first;
  130.  
  131. 				dfsRecursiveHelper(val.first, adjList, visited, timeStamps, timer, printVertices, useTimeStamps);
  132.  
  133. 				if(printVertices)	
  134. 					cout<<"\n";
  135. 			}
  136. 	}
  137.  
  138. 	void findStronglyConnectedComponents(){
  139.  
  140. 		vector<bool> visited(n, false);
  141. 		vector<pair<int, pair<int, int>>> timeStamps(n);
  142.  
  143. 		bool printVertices = false, useTimeStamps = true;
  144.  
  145. 		for(int i = 0; i < n; ++i){
  146. 			timeStamps[i].first = i;
  147. 		}
  148.  
  149. 		dfsRecursive(adj, timeStamps, visited, printVertices, useTimeStamps);
  150.  
  151. 		sort(timeStamps.begin(), timeStamps.end(), 
  152. 			[](pair<int, pair<int, int>> &a, 
  153. 				pair<int, pair<int, int>> &b){ return a.second.second > b.second.second; });
  154.  
  155. 		// for(auto val: timeStamps){
  156. 		// 	cout<<"Node-"<<val.first<<" | d: "<<val.second.first<<" | f: "<<val.second.second<<"\n";
  157. 		// }
  158.  
  159. 		/*================ Transpose graph ===============*/
  160. 		vector<vector<int>> adjTranspose(n);
  161.  
  162. 		for(int i=0; i < n; ++i){
  163. 			for(auto node: adj[i]){
  164. 				adjTranspose[node].push_back(i);
  165. 			}
  166. 		}
  167. 		/*================ Transpose graph ===============*/
  168.  
  169.  
  170. 		/*================ DFS on Transpose graph ================*/
  171. 		printVertices = true, useTimeStamps = false;
  172. 		visited = vector<bool>(n, false);
  173.  
  174. 		dfsRecursive(adjTranspose, timeStamps, visited, printVertices, useTimeStamps);
  175. 		/*================ DFS on Transpose graph ================*/
  176. 	}
  177.  
  178. 	void dfsPath(int source){
  179. 		int connectedComponents = 0;
  180.  
  181. 		vector<bool> visited(n, false);
  182. 		vector<int> pathFromSourcePredecessor(n, -1);
  183.  
  184. 		dfs(visited, pathFromSourcePredecessor, source);
  185.  
  186. 		for(int i = 0; i < n; ++i){
  187. 			if(!visited[i]){
  188. 				cout<<"----------------------------------------------------\n";
  189. 				dfs(visited, pathFromSourcePredecessor, i);
  190. 				++connectedComponents;
  191. 			}
  192. 		}
  193.  
  194. 		cout<<"----------------------------------------------------\n";
  195. 		if(!connectedComponents){
  196. 			cout<<"The graph is connected.\n";
  197. 		}
  198. 		else{
  199. 			cout<<"The graph has "<<connectedComponents+1<<" connected components.\n";
  200. 		}
  201.  
  202. 	}
  203.  
  204. 	void dfs(vector<bool> &visited, vector<int> &pathFromSourcePredecessor, int source){
  205. 		stack<int> st;
  206.  
  207. 		st.push(source);
  208. 		visited[source] = true;
  209.  
  210. 		cout<<"DFS path from the source:";
  211.  
  212. 		while(!st.empty()){
  213. 			int currVertex = st.top(); st.pop();
  214.  
  215. 			cout<<(source == currVertex ? "":"->")<<currVertex;
  216.  
  217. 			int prevVertex = currVertex;
  218.  
  219. 			for(auto node: adj[currVertex]){
  220. 				if(!visited[node]){
  221. 					st.push(node);
  222. 					visited[node] = true;
  223.  
  224. 					pathFromSourcePredecessor[node] = prevVertex;
  225. 					prevVertex = node;
  226. 				}
  227. 			}
  228.  
  229. 		}
  230.  
  231. 		cout<<"\nPath from source "<<source<<",\n";
  232.  
  233. 		for(int i=0; i < n; ++i){
  234. 			if(i != source){
  235. 				cout<<"----------------------------------------------------\n";
  236. 				cout<<"To node-"<<i<<" is: ";
  237.  
  238. 				int dest = i;
  239. 				stack<int> path;
  240.  
  241. 				while(true){
  242. 					if(dest == source || dest == -1)
  243. 						break;
  244.  
  245. 					path.push(dest);
  246. 					dest = pathFromSourcePredecessor[dest];
  247. 				}
  248.  
  249. 				if(dest == -1){
  250. 					cout<<"\n\tNo path exits from the given source in this "
  251. 					<<(isDirected ? "directed graph.\n": "undirected graph.\n");
  252.  
  253. 					if(!isDirected)
  254. 						cout<<"\tThe graph is disconnected.\n";
  255. 				}
  256. 				else{
  257. 					int pathLength = 0;
  258.  
  259. 					cout<<source;
  260.  
  261. 					while(!path.empty()){
  262. 						cout<<"->"<<path.top(); 
  263. 						path.pop();
  264. 						++pathLength;
  265. 					}
  266.  
  267. 					cout<<"\n\tThe path length is: "<<pathLength<<"\n";
  268. 				}
  269. 			}
  270. 		}
  271. 	}
  272.  
  273. 	void bfsPath(int source){
  274. 		int connectedComponents = 0;
  275.  
  276. 		vector<bool> visited(n, false);
  277. 		vector<int> shortestPathFromSourcePredecessor(n, -1);
  278.  
  279. 		bfs(visited, shortestPathFromSourcePredecessor, source);
  280.  
  281. 		for(int i = 0; i < n; ++i){
  282. 			if(!visited[i]){
  283. 				cout<<"----------------------------------------------------\n";
  284. 				bfs(visited, shortestPathFromSourcePredecessor, i);
  285. 				++connectedComponents;
  286. 			}
  287. 		}
  288.  
  289. 		cout<<"----------------------------------------------------\n";
  290. 		if(!connectedComponents){
  291. 			cout<<"The graph is connected.\n";
  292. 		}
  293. 		else{
  294. 			cout<<"The graph has "<<connectedComponents+1<<" connected components.\n";
  295. 		}
  296. 	}
  297.  
  298. 	void bfs(vector<bool> &visited, vector<int> &shortestPathFromSourcePredecessor, int source){
  299. 		queue<int> qu;
  300.  
  301. 		qu.push(source);
  302. 		visited[source] = true;
  303.  
  304. 		cout<<"BFS path from source:";
  305.  
  306. 		while(!qu.empty()){
  307. 			int currVertex = qu.front();
  308. 			qu.pop();
  309.  
  310. 			for(auto node: adj[currVertex]){
  311. 				if(!visited[node]){
  312. 					qu.push(node);
  313. 					visited[node] = true;
  314.  
  315. 					shortestPathFromSourcePredecessor[node] = currVertex;
  316. 				}
  317. 			}
  318.  
  319. 			cout<<(source == currVertex ? "":"->")<<currVertex;
  320. 		}
  321.  
  322. 		cout<<"\nShortest path from source "<<source<<",\n";
  323.  
  324. 		for(int i=0; i < n; ++i){
  325. 			if(i != source){
  326. 				cout<<"----------------------------------------------------\n";
  327. 				cout<<"To node-"<<i<<" is: ";
  328.  
  329. 				int dest = i;
  330. 				stack<int> path;
  331.  
  332. 				while(true){
  333. 					if(dest == source || dest == -1)
  334. 						break;
  335.  
  336. 					path.push(dest);
  337. 					dest = shortestPathFromSourcePredecessor[dest];
  338. 				}
  339.  
  340. 				if(dest == -1){
  341. 					cout<<"\n\tNo path exits from the given source in this "
  342. 					<<(isDirected ? "directed graph.\n": "undirected graph.\n");
  343.  
  344. 					if(!isDirected)
  345. 						cout<<"\tThe graph is disconnected.\n";
  346. 				}
  347. 				else{
  348. 					int pathLength = 0;
  349.  
  350. 					cout<<source;
  351.  
  352. 					while(!path.empty()){
  353. 						cout<<"->"<<path.top(); 
  354. 						path.pop();
  355. 						++pathLength;
  356. 					}
  357.  
  358. 					cout<<"\n\tThe path length is: "<<pathLength<<"\n";
  359. 				}
  360.  
  361. 			}
  362. 		}
  363. 	}
  364.  
  365. };
  366.  
  367. int main() { 
  368. 	int opt, isDir, src, dest; 
  369.  
  370. 	cin>>opt;
  371. 	cout<<"Please enter # vertices in the graph: "<<opt<<"\n"; 
  372. 	cin>>isDir;
  373. 	cout<<"Is the graph directed(1/0)? "<<isDir<<"\n"; 
  374.  
  375. 	Graph g(opt, isDir); 
  376.  
  377. 	cout<<"Operations available on graph:\n"; 
  378. 	cout<<"1. Insert an edge\n2. Delete an edge\n3. Print graph\n"
  379. 	"4. BFS Path\n5. DFS Path\n6. Find Connected componets\n7. Exit\n"; 
  380. 	cout<<"****************************************************\n"; 
  381. 	while(true){ 
  382. 		cin>>opt; 
  383. 		switch(opt){ 
  384. 			case 1:
  385. 				cin>>src>>dest; 
  386. 				cout<<"Enter the source and destination to insert edge,\n"
  387. 				"Source: " <<src<<" Destination: "<<dest<<"\n"; g.insertEdge(src, dest); 
  388. 				break;
  389. 			case 2:
  390. 				cin>>src>>dest;
  391. 				cout<<"Enter the source and destination to delete edge,\n"
  392. 				"Source: " <<src<<" Destination: "<<dest<<"\n"; g.deleteEdge(src, dest);
  393. 				break;
  394. 			case 3: 
  395. 				g.displayGraph();
  396. 				break;
  397. 			case 4:
  398. 				cin>>src;
  399. 				g.bfsPath(src);
  400. 				break;
  401. 			case 5:
  402. 				cin>>src;
  403. 				g.dfsPath(src);
  404. 				break;
  405. 			case 6:
  406. 				g.findStronglyConnectedComponents();
  407. 				break;
  408. 			case 7:
  409. 				exit(0);
  410. 		} 
  411. 		cout<<"****************************************************\n";
  412. 	} 
  413.  
  414. 	return 0;
  415. }
Success #stdin #stdout 0s 4432KB
comments (?)
stdin
copy 
8 1
1 0 1
1 1 2
1 1 3
1 1 4
1 2 6
1 3 0
1 3 2
1 4 5
1 4 6
1 5 4
1 5 7
1 6 2
1 6 7
1 7 7
6
7
stdout
copy 
Please enter # vertices in the graph: 8
Is the graph directed(1/0)? 1
Operations available on graph:
1. Insert an edge
2. Delete an edge
3. Print graph
4. BFS Path
5. DFS Path
6. Find Connected componets
7. Exit
****************************************************
Enter the source and destination to insert edge,
Source: 0 Destination: 1
****************************************************
Enter the source and destination to insert edge,
Source: 1 Destination: 2
****************************************************
Enter the source and destination to insert edge,
Source: 1 Destination: 3
****************************************************
Enter the source and destination to insert edge,
Source: 1 Destination: 4
****************************************************
Enter the source and destination to insert edge,
Source: 2 Destination: 6
****************************************************
Enter the source and destination to insert edge,
Source: 3 Destination: 0
****************************************************
Enter the source and destination to insert edge,
Source: 3 Destination: 2
****************************************************
Enter the source and destination to insert edge,
Source: 4 Destination: 5
****************************************************
Enter the source and destination to insert edge,
Source: 4 Destination: 6
****************************************************
Enter the source and destination to insert edge,
Source: 5 Destination: 4
****************************************************
Enter the source and destination to insert edge,
Source: 5 Destination: 7
****************************************************
Enter the source and destination to insert edge,
Source: 6 Destination: 2
****************************************************
Enter the source and destination to insert edge,
Source: 6 Destination: 7
****************************************************
Enter the source and destination to insert edge,
Source: 7 Destination: 7
****************************************************
The nodes in strongly connected component 1: 0->1->3
The nodes in strongly connected component 2: 4->5
The nodes in strongly connected component 3: 2->6
The nodes in strongly connected component 4: 7
****************************************************
https://ideone.com/bivKi0
Strongly connected components using timestamps || Time complexity: O(m log n)
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!