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. 		// 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, bool &useStack,
  87. 							vector<int> &ans){
  88.  
  89. 		visited[src] = true;
  90.  
  91. 		for(auto node: adjList[src]){
  92. 			// if(!useStack && node == src){
  93. 			// 	ans.push_back(node);
  94. 			// }
  95. 			// else 
  96. 			if(isSafe(node) && !visited[node]){
  97.  
  98. 				dfsRecursiveHelper(node, st, adjList, visited, useStack, ans);
  99.  
  100. 				if(useStack){
  101. 					st.push(node);
  102. 				}
  103. 				else{
  104. 					ans.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. 		vector<int> ans;
  117.  
  118. 		int maxCycleSum = INT_MIN;
  119.  
  120.  
  121. 		if(useStack){
  122. 			for(int i = 0; i < n; ++i){
  123. 				if(isSafe(i) && !visited[i]){
  124.  
  125. 					dfsRecursiveHelper(i, st, adjList, visited, useStack, ans);
  126.  
  127. 					st.push(i);
  128. 				}
  129. 			}
  130. 		}
  131. 		else{
  132. 			while(!st.empty()){
  133. 				int i = st.top();
  134.  
  135. 				if(isSafe(i) && !visited[i]){
  136.  
  137. 					dfsRecursiveHelper(i, st, adjList, visited, useStack, ans);
  138.  
  139. 					if(ans.size() > 0){
  140. 						cout<<"The nodes in strongly connected component "<<++connectedComponents<<": "<<i;
  141.  
  142. 						for(auto val: ans)
  143. 							cout<<"->"<<val;
  144. 						cout<<"\n";
  145.  
  146. 						int s = accumulate(ans.begin(), ans.end(), 0) + i;
  147.  
  148. 						if(s > maxCycleSum)
  149. 							maxCycleSum = s;
  150.  
  151. 						cout<<"Cycle sum: "<<s;
  152.  
  153. 						cout<<"\n------------------------------------------------------------------\n";
  154. 					}
  155.  
  156. 					ans.clear();
  157. 				}
  158.  
  159. 				st.pop();
  160. 			}
  161.  
  162. 			for(int i = 0; i < n; ++i){
  163. 				for(auto &node: adjList[i]){
  164. 					if(visited[node] && node == i){
  165. 						cout<<"The nodes in strongly connected component(self loop) "<<++connectedComponents<<": "<<i;
  166.  
  167. 						cout<<"->"<<node<<"\n";
  168.  
  169. 						if(i > maxCycleSum)
  170. 							maxCycleSum = i;
  171.  
  172. 						cout<<"Cycle sum: "<<i;
  173.  
  174. 						cout<<"\n------------------------------------------------------------------\n";
  175. 					}
  176. 				}
  177. 			}
  178. 		}
  179.  
  180.  
  181. 		if(!useStack && connectedComponents){
  182. 			cout<<"Max cycle sum: "<<maxCycleSum<<"\n";
  183. 			cout<<"The directed graph has "<<connectedComponents<<" strongly connected components.\n";
  184. 		}
  185. 		else if(!useStack){
  186. 			cout<<"------------------------------------------------------------------\n";
  187. 			cout<<"The directed graph has no strongly connected components.\n";
  188. 			cout<<"Max cycle sum: -1\n";
  189. 		}
  190. 	}
  191.  
  192. 	void findStronglyConnectedComponents(){
  193.  
  194. 		/*================ DFS on actual graph ================*/
  195. 		vector<bool> visited(n, false);
  196. 		stack<int> st;
  197.  
  198. 		bool printVertices = false, useStack = true;
  199.  
  200. 		dfsRecursive(adj, visited, st, useStack);
  201. 		/*================ DFS on actual graph ================*/
  202.  
  203. 		/*================ Transpose graph ===============*/
  204. 		vector<vector<int>> adjTranspose(n);
  205.  
  206. 		for(int i=0; i < n; ++i){
  207. 			for(auto node: adj[i]){
  208. 				if(isSafe(node))
  209. 					adjTranspose[node].push_back(i);
  210. 			}
  211. 		}
  212. 		/*================ Transpose graph ===============*/
  213.  
  214.  
  215. 		/*================ DFS on Transpose graph ================*/
  216. 		printVertices = true, useStack = false;
  217. 		visited = vector<bool>(n, false);
  218.  
  219. 		dfsRecursive(adjTranspose, visited, st, useStack);
  220. 		/*================ DFS on Transpose graph ================*/
  221. 	}
  222.  
  223. 	bool isSafe(int idx){
  224. 		return -1 < idx && idx < n;
  225. 	}
  226.  
  227. };
  228.  
  229. int main() { 
  230. 	int t;
  231. 	cin>>t;
  232. 	while(t--){
  233. 		int n, v; cin>>n;
  234. 		Graph g(n, 1);
  235.  
  236. 		for(int i=0; i < n; ++i){
  237. 			cin>>v;
  238. 			g.insertEdge(i, v);
  239. 		}
  240.  
  241. 		g.findStronglyConnectedComponents();
  242. 		cout<<"==================================================================\n";
  243. 	}
  244. 	return 0;
  245. }
Success #stdin #stdout 0s 4536KB
comments (?)
stdin
copy 
5
13
4 5 1 6 5 10 1 5 10 10 -1 12 -1
15
5 3 3 9 8 4 1 3 7 0 11 10 10 10 10
9
2 2 5 4 8 3 2 6 6
201
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 0 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 -1
10
4 5 1 6 5 2 1 5 10 10

"Output - 1"
-1
36
28
4950
8

"Input - 2"
1
23
4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21

"Output - 2"
45
stdout
copy 
Either of the vertices doesn't exists in the graph.
Either of the vertices doesn't exists in the graph.
------------------------------------------------------------------
The directed graph has no strongly connected components.
Max cycle sum: -1
==================================================================
The nodes in strongly connected component 1: 10->11
Cycle sum: 21
------------------------------------------------------------------
The nodes in strongly connected component 2: 0->5->4->8->7->3->9
Cycle sum: 36
------------------------------------------------------------------
Max cycle sum: 36
The directed graph has 2 strongly connected components.
==================================================================
The nodes in strongly connected component 1: 2->5->3->4->8->6
Cycle sum: 28
------------------------------------------------------------------
Max cycle sum: 28
The directed graph has 1 strongly connected components.
==================================================================
Either of the vertices doesn't exists in the graph.
The nodes in strongly connected component 1: 0->1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->21->22->23->24->25->26->27->28->29->30->31->32->33->34->35->36->37->38->39->40->41->42->43->44->45->46->47->48->49->50->51->52->53->54->55->56->57->58->59->60->61->62->63->64->65->66->67->68->69->70->71->72->73->74->75->76->77->78->79->80->81->82->83->84->85->86->87->88->89->90->91->92->93->94->95->96->97->98->99
Cycle sum: 4950
------------------------------------------------------------------
The nodes in strongly connected component(self loop) 2: 102->102
Cycle sum: 102
------------------------------------------------------------------
Max cycle sum: 4950
The directed graph has 2 strongly connected components.
==================================================================
Either of the vertices doesn't exists in the graph.
Either of the vertices doesn't exists in the graph.
The nodes in strongly connected component 1: 5->2->1
Cycle sum: 8
------------------------------------------------------------------
Max cycle sum: 8
The directed graph has 1 strongly connected components.
==================================================================
https://ideone.com/LHHzzY
Cycle detection and max cycle nodes sum using Kosaraju's algorithm || 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!