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

"Input - 2 for connected components in undirected graph. Replace below input with above input if required."
6
0
1 0 1
1 0 3
1 1 2
1 3 1
1 2 3
1 4 5
1 5 5
3
4 0
6
stdout 
Please enter # vertices in the graph: 10
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 strongly connected componets(If di-graph)
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: 8
****************************************************
Enter the source and destination to insert edge,
Source: 7 Destination: 7
****************************************************
Enter the source and destination to insert edge,
Source: 7 Destination: 9
****************************************************
Total # edges in the graph: 16
The edges from vertex 0:->1
The edges from vertex 1:->2->3->4
The edges from vertex 2:->6
The edges from vertex 3:->0->2
The edges from vertex 4:->5->6
The edges from vertex 5:->4->7
The edges from vertex 6:->2->7
The edges from vertex 7:->8->7->9
The edges from vertex 8:
The edges from vertex 9:
****************************************************
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->7
The directed graph has 4 strongly connected components.
****************************************************
https://ideone.com/CcvSqG
Graph Adjacency List
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!