1  #include <iostream>
  2  #include <vector>
  3  #include <algorithm>
  4  
  5  //test0515789798878979879879887978979879879
  6  using namespace std;
  7  
  8  void topologicalSortUtil(const vector<vector<int>> &graph, vector<int> &indegree, vector<char> &result, vector<bool> &visited)
  9  {
 10      bool flag = false;
 11  
 12      for (int i = 0; i < graph.size(); ++i)
 13      {
 14          if (!visited[i] && indegree[i] == 0)
 15          {
 16              visited[i] = true;
 17              result.push_back('A' + i);
 18  
 19              for (int j = 0; j < graph.size(); ++j)
 20              {
 21                  if (graph[i][j] == 1)
 22                  {
 23                      --indegree[j];
 24                  }
 25              }
 26  
 27              topologicalSortUtil(graph, indegree, result, visited);
 28  
 29              visited[i] = false;
 30              result.pop_back();
 31  
 32              for (int j = 0; j < graph.size(); ++j)
 33              {
 34                  if (graph[i][j] == 1)
 35                  {
 36                      ++indegree[j];
 37                  }
 38              }
 39  
 40              flag = true;
 41          }
 42      }
 43  
 44      if (!flag)
 45      {
 46          for (char ch : result)
 47          {
 48              cout << ch << " ";
 49          }
 50          cout << endl;
 51      }
 52  }
 53  
 54  void topologicalSort(const vector<vector<int>> &graph, const vector<char> &vertexLabels)
 55  {
 56      vector<int> indegree(graph.size(), 0);
 57  
 58      // Calculate in-degree for each vertex
 59      for (int i = 0; i < graph.size(); ++i)
 60      {
 61          for (int j = 0; j < graph.size(); ++j)
 62          {
 63              if (graph[j][i] == 1)
 64              {
 65                  ++indegree[i];
 66              }
 67          }
 68      }
 69  
 70      vector<bool> visited(graph.size(), false);
 71      vector<char> result;
 72  
 73      topologicalSortUtil(graph, indegree, result, visited);
 74  }
 75  
 76  int main()
 77  {
 78      int vertices;
 79      cout << "Enter the number of vertices in the graph: ";
 80      cin >> vertices;
 81  
 82      vector<vector<int>> graph(vertices, vector<int>(vertices));
 83      vector<char> vertexLabels(vertices);
 84  
 85      cout << "Enter the adjacency matrix:\n";
 86      for (int i = 0; i < vertices; ++i)
 87      {
 88          for (int j = 0; j < vertices; ++j)
 89          {
 90              cin >> graph[i][j];
 91          }
 92      }
 93  
 94      cout << "Enter the labels for the vertices (characters):\n";
 95      for (int i = 0; i < vertices; ++i)
 96      {
 97          cin >> vertexLabels[i];
 98      }
 99  
100      cout << "\nAll possible topological orders:\n";
101      topologicalSort(graph, vertexLabels);
102  
103      return 0;
104  }