Cannot iterate through unordered_map. Works well in my own computer.


  • 0
    Z

    My code works well on my own computer but here it since that it only executes one DFS and goes out of for loop.

          for (auto it: graph) {
              if (marked.count(it.first) == 0) {
                  DFS(it.first);
              }
          }
    

    I tested that my graph is the same after DFS. My DFS is like this:

      void DFS(char v) {
          marked.insert(v);
          for (int i = 0; i < graph[v].size(); i++) {
              if (marked.count(graph[v][i]) == 1 && finished.count(graph[v][i]) == 0) {
                  is_DAG = false;
                  return;
              }
              if (marked.count(graph[v][i]) == 0) {
                  DFS(graph[v][i]);
              }
          }
          finishing_time.push(v);
          finished.insert(v);
      }
    

    My whole code:

    class Solution {
    public:
        string alienOrder(vector<string>& words) {
          string str;
          if (words.empty()) {
              return str;
          }
          is_DAG = true;
          CreateGraph(words);
          str = TopologicalSort();
         // ShowGraph();
          return str;
        }
        void ShowGraph() {
          for (auto it = graph.begin(); it != graph.end(); it++) {
            cout << it->first << ": ";
            for (int i = 0; i < it->second.size(); i++) {
              cout << it->second[i] << " ";
            }
            cout << endl;
          }
        }
    private: 
      void CreateGraph(vector<string>& words) {
          if (words.empty()) {
              return;
          }
          char c = words[0][0];
          vector<string> group;
          for (int i = 0; i < words.size(); i++) {
              if (words[i][0] == c) {
                string str = words[i];
                str.erase(str.begin());
                if (!str.empty()) {
                  group.push_back(str);
                }
              }
              if (words[i][0] != c || i == words.size() - 1) {
                  if (group.size() >= 2) {
                    CreateGraph(group);   
                  }
                  if (words[i][0] != c) {
                      graph[c].push_back(words[i][0]);
                      c = words[i][0];
                      group.clear();
                      string str = words[i];
                      str.erase(str.begin());
                      if (!str.empty()) {
                        group.push_back(str);
                      }
                  }
              }
          }
      }
      string TopologicalSort() {
          //ShowGraph();
          string str;
          for (auto it: graph) {
              if (marked.count(it.first) == 0) {
                  DFS(it.first);
              }
          }
          if (!is_DAG) {
              return str;
          }
          while (!finishing_time.empty()) {
              str += finishing_time.top();
              finishing_time.pop();
          }
          return str;
      }
      void DFS(char v) {
          marked.insert(v);
          for (int i = 0; i < graph[v].size(); i++) {
              if (marked.count(graph[v][i]) == 1 && finished.count(graph[v][i]) == 0) {
                  is_DAG = false;
                  return;
              }
              if (marked.count(graph[v][i]) == 0) {
                  DFS(graph[v][i]);
              }
          }
          finishing_time.push(v);
          finished.insert(v);
      }
      unordered_map<char, vector<char> > graph;
      stack<char> finishing_time;
      unordered_set<char> marked;
      unordered_set<char> finished;
      bool is_DAG;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.