Amazon Interview Question
SDE1sCountry: United States
//Simple DFS approach
int components(){
int count = 0;
for(Node n : Graph.vertices()){
if(!visited(n)){
count++;
DFS(n);
}
}
return count;
}
void DFS(Node node){
visit(node);
for(Node adj : node.getAdjacentNodes()){
DFS(adj);
}
}
//To implement visited we can use an array or Map\Dictionary
int n;
- Anonymous September 05, 2015vector<int> g[MAXN];
bool used[MAXN];
vector<int> comp;
int res = 0; //Number Of Connected Components
void dfs (int v) {
used[v] = true;
comp.push_back (v);
for (size_t i=0; i<g[v].size(); ++i) {
int to = g[v][i];
if (! used[to])
dfs (to);
}
}
void find_comps() {
for (int i=0; i<n; ++i)
used[i] = false;
for (int i=0; i<n; ++i)
if (! used[i]) {
comp.clear();
dfs (i);
res++;
}
}