fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <unordered_map>
  5.  
  6. using namespace std;
  7.  
  8. /**
  9.  * Recursive helper for DFS topological sort and cycle detection
  10.  * state[u] == 0: Unvisited
  11.  * state[u] == 1: Visiting (in current recursion stack)
  12.  * state[u] == 2: Visited (fully processed)
  13.  */
  14. bool buildDFS(const string& u, 
  15.               unordered_map<string, vector<string>>& adj, 
  16.               unordered_map<string, int>& state, 
  17.               vector<string>& order) {
  18.  
  19.     state[u] = 1; // Mark as "Visiting"
  20.  
  21.     for (const string& v : adj[u]) {
  22.         if (state[v] == 1) return false; // Cycle detected!
  23.         if (state[v] == 0) {
  24.             if (!buildDFS(v, adj, state, order)) return false;
  25.         }
  26.     }
  27.  
  28.     state[u] = 2; // Mark as "Visited"
  29.     order.push_back(u); // Add to build order after all dependencies are done
  30.     return true;
  31. }
  32.  
  33. /**
  34.  * Main function to get the build order
  35.  */
  36. vector<string> getBuildOrder(string target, unordered_map<string, vector<string>>& adj) {
  37.     vector<string> order;
  38.     unordered_map<string, int> state; 
  39.  
  40.     if (buildDFS(target, adj, state, order)) {
  41.         return order;
  42.     }
  43.     return {}; // Return empty if cycle found
  44. }
  45.  
  46. int main() {
  47.     // Adjacency list representation of the prompt graph
  48.     unordered_map<string, vector<string>> adj = {
  49.         {"Service", {"Adapters", "Core", "Utils"}},
  50.         {"Adapters", {"Interfaces"}},
  51.         {"Core", {"Types"}},
  52.         {"Utils", {"Types"}},
  53.         {"Interfaces", {"Types"}},
  54.         {"Types", {}}
  55.     };
  56.  
  57.     vector<string> result = getBuildOrder("Service", adj);
  58.  
  59.     if (result.empty()) {
  60.         cout << "Error: Circular dependency detected!" << endl;
  61.     } else {
  62.         for (size_t i = 0; i < result.size(); ++i) {
  63.             cout << result[i] << (i == result.size() - 1 ? "" : " > ");
  64.         }
  65.         cout << endl;
  66.     }
  67.  
  68.     return 0;
  69. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Types > Interfaces > Adapters > Core > Utils > Service
https://ideone.com/m0uzBk
language:
C++ (gcc 8.3)
created:
1 day 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!