fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> countVisitedShops(vector<int>& paths) {
  5.     int n = paths.size();
  6.     vector<int> dp(n, 0), state(n, 0); // 0=unvisited, 1=visiting, 2=done
  7.     vector<int> stackOrder;
  8.  
  9.     function<int(int)> dfs = [&](int u) -> int {
  10.         if (state[u] == 2) return dp[u];       // already computed
  11.         if (state[u] == 1) {                   // found cycle
  12.             int cnt = 1;
  13.             for (int i = stackOrder.size() - 1; i >= 0; i--) {
  14.                 cnt++;
  15.                 if (stackOrder[i] == u) break;
  16.             }
  17.             dp[u] = cnt - 1;
  18.             return dp[u];
  19.         }
  20.  
  21.         state[u] = 1;
  22.         stackOrder.push_back(u);
  23.         int v = paths[u];
  24.         int res = dfs(v);
  25.         if (dp[u] == 0) dp[u] = res + (state[v] != 1 ? 1 : 0);
  26.         state[u] = 2;
  27.         stackOrder.pop_back();
  28.         return dp[u];
  29.     };
  30.  
  31.     for (int i = 0; i < n; i++)
  32.         if (state[i] == 0) dfs(i);
  33.  
  34.     return dp;
  35. }
  36.  
  37. int main() {
  38.     int n;
  39.     cin >> n;
  40.     vector<int> paths(n);
  41.     for (int i = 0; i < n; i++) cin >> paths[i];
  42.  
  43.     vector<int> result = countVisitedShops(paths);
  44.     for (int x : result) cout << x << " ";
  45.     cout << endl;
  46.     return 0;
  47. }
  48.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/G6mTOV
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (clang 8.0)

					

					

						
created:
								
						
17 days ago

					

					

						
visibility:

						

							 public																												
							
							

								
							

						

					

										
										

					
					 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!