Minimum Vertices to Traverse Directed Graph, C++ (gcc)

Minimum Vertices to Traverse Directed Graph

/*29 Minimum Vertices to Traverse Directed Graph
Given a directed grapjh, represented in a two dimension array, 
output a list of points that can be used to travese every
points with the least number of visited vertices.
*/
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <queue>

using namespace std;

class Solution {
    map<int, set<int>> m; 
    map<int, set<int>> degree; // in-degree 
public: 
    vector<int> minVertices_DFS(vector<vector<int>>& edges, int n) {
        m.clear(); 
        for(auto e: edges) {
            int x = e[0], y = e[1];
            m[x].insert(y); 
            degree[y].insert(x); 
        }
         
        vector<int> res; 
        set<int> visited; 
        for(int i=0; i<n; i++) {         // 1st to visit in-degree == 0
            if(degree.count(i)==0 && visited.count(i) == 0) {  
                res.push_back(i); 
                DFS(i, visited); 
            }
        }
        
        for(int i=0; i<n; i++) {         // 2nd to visit one in a loop, still not visited 
            if(visited.count(i)==0) {
                res.push_back(i);
                DFS(i, visited); 
            }
        }
        return res; 
    }
    
    void DFS(int i, set<int>& visited){
        if(visited.count(i)) 
            return; 
        visited.insert(i);    // visit i
        for(auto x: m[i])     // visit i's neighbors 
            DFS(x, visited);
    }
    
  vector<int> BFS(vector<vector<int>>& edges, int n){
      // init graph
      m.clear(); 
      for(auto e: edges){
        int x = e[0], y = e[1];
        m[x].insert(y);
        degree[y].insert(x);
      }

set<int> q;
      vector<int> res; 
      set<int> visited; 
      for(int i=0; i<n; i++){
        if(degree.count(i) == 0){
          res.push_back(i); 
          q.insert(i);
        }
      }
      
      while(q.size() || degree.size()){
        
        if(q.size()==0 && degree.size()){ // there is a cycle, has to handle this first 
          int i = degree.begin()->first; // can use any one 
          res.push_back(i); // easy to forget 
          q.insert(i);
        }
        
        int x = *q.begin();
        q.erase(x);    
        if(visited.count(x)) continue; // already visited 
        visited.insert(x);
        degree.erase(x);
        
        for(int y: m[x]){ // visit x's neighbors 
            q.insert(y);
        }
            
      }
      return res;

}

void print(vector<int>& res) {
        for(auto x: res) {
            cout << x << " " ;
        }
        cout << endl;
    }
};

int main() {
       
    vector<vector<int>> edges = {{0,1}, {1,0}, {2,3}};
    int n = 4; // [2,0]
    
    edges =  {{2,9},{3,3},{3,5},{3,7},{4,8},{5,8},{6,6},{7,4},{8,7},{9,3},{9,6}};
    n = 10; // expected result [0,1,2]
    
    edges =  {{0,1},{1,2},{2,3},{3,4},{4,0},{5,6},{6,7},{7,8},{8,9},{9,5}};
    n = 10; // expected  [5,0]
    
    edges =  {{0,1},{1,2},{2,3},{3,4},{4,0},{7,6},{6,8},{8,6}};
    n = 10; // expected  [5,7,9,0]
    
    Solution s; 
    vector<int> res = s.minVertices(edges, n);
    s.print(res); 
  
    Solution s2;
    vector<int> res2 = s2.BFS(edges, n);
    s2.print(res2);
    
    
    return 0; 
}


run \| edit \| history \| help	0