Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Minimum Vertices to Traverse Directed Graph
Language:
Ada
Assembly
Bash
C#
C++ (gcc)
C++ (clang)
C++ (vc++)
C (gcc)
C (clang)
C (vc)
Client Side
Clojure
Common Lisp
D
Elixir
Erlang
F#
Fortran
Go
Haskell
Java
Javascript
Kotlin
Lua
MySql
Node.js
Ocaml
Octave
Objective-C
Oracle
Pascal
Perl
Php
PostgreSQL
Prolog
Python
Python 3
R
Rust
Ruby
Scala
Scheme
Sql Server
Swift
Tcl
Visual Basic
Layout:
Vertical
Horizontal
/*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; }
g++
Show compiler warnings
[
+
] Compiler args
[
+
]
Show input
Compilation time: 0.82 sec, absolute running time: 0.07 sec, cpu time: 0.01 sec, memory peak: 3 Mb, absolute service time: 0,9 sec
edit mode
|
history
|
discussion
5 7 9 0