# [C++] Clean Code - 2 Solution - DFS & BFS

• DFS

``````class Solution {
public:
vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
vector<int> killed;
map<int, set<int>> children;
for (int i = 0; i < pid.size(); i++) {
children[ppid[i]].insert(pid[i]);
}
killAll(kill, children, killed);
return killed;
}

private:
void killAll(int pid, map<int, set<int>>& children, vector<int>& killed) {
killed.push_back(pid);
for (int child : children[pid]) {
killAll(child, children, killed);
}
}
};
``````

BFS

``````class Solution {
public:
vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
vector<int> killed;
map<int, set<int>> children;
for (int i = 0; i < pid.size(); i++) {
children[ppid[i]].insert(pid[i]);
}

queue<int> q;
q.push(kill);
while (!q.empty()) {
int p = q.front(); q.pop();
killed.push_back(p);
for (int child : children[p]) {
q.push(child);
}
}

return killed;
}
};
``````

• Here is my C++ code. Same idea, but using unordered_map and vector to improve performance.

``````vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
unordered_map<int, vector<int>> pros;
for (int i = 0; i < pid.size(); ++i)
pros[ppid[i]].push_back(pid[i]);
vector<int> ans;
queue<int> q;
q.push(kill);
while (!q.empty()) {
ans.push_back(q.front());
q.pop();
for (int m:pros[ans.back()])
q.push(m);
}
return ans;
}
``````

• Same idea here (162ms). I think use `vector` to perform `queue` can improve the solution. Because `vector` can insert another `vector` in one time. Therefore, we don't have to go through the every child process to push them into the `queue`.

``````class Solution {
public:
vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
unordered_map<int, vector<int>> hm;
for ( int i = 0; i < pid.size(); i++ ) {
hm[ppid[i]].push_back(pid[i]);
}

if ( hm[0].back() == kill ) return pid;
vector<int> ret(1,kill);

vector<int> Q; // perform as queue
Q.push_back(kill);
while( !Q.empty() ) {
int key = Q.front();
Q.erase(Q.begin());
if ( hm.find(key) != hm.end() ) {
Q.insert(Q.end(), hm[key].begin(), hm[key].end());
ret.insert(ret.end(), hm[key].begin(), hm[key].end());
}
}
return ret;
}
};
``````

• @sijiec I think append a vector with another vector is an operation with time complexity O(n), and erase an element at the front is also O(n).

• hash + bfs

``````    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
unordered_map<int, vector<int>> m;
for (int i = 0; i < pid.size(); ++i) {
m[ppid[i]].push_back(pid[i]);
}

vector<int> res;
res.push_back(kill);
int i = 0;
while(i < res.size()) {
int p = res[i++];
if (m.count(p)) {
for(auto pp : m[p]) {
res.push_back(pp);
}
m.erase(p);
}
}
return res;
}
``````

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