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>

using namespace std;

class Solution {
    map<int, set<int>> m; 
    map<int, set<int>> degree; // in-degree 
public: 
    vector<int> minVertices(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);
    }
    
    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); 
    
    
    return 0; 
}


run \| edit \| history \| help	0