# HELP: my c++ solution based on DFS which can only pass 33/34 case

• My solution is based on DFS, when it discovered a vertex which has already been in the stack, in will change the variable 'circle' to false, which means it has circle. But it can only pass 33/34 case, I don't know where I made a mistake.

WHO CAN HELP ME, I AM GOING TO BE MAD!!!

Thank you very much

class Solution {
public:

``````bool canFinish(int numCourses, vector<pair<int, int> >& prerequisites) {
multimap<int, int> G; // Use Hash map to store the graph.
bool circle = true;

for (size_t i = 0; i < prerequisites.size(); i++) {
G.insert(prerequisites[i]); // store the graph using hash multi_map
}

int* visited = new int[numCourses];
memset (visited, 0, numCourses * sizeof(visited[0])); // visited[i] = 0 represents vertex i has not been discovered

for ( int i = 0; i < numCourses; i++ ) {
if ( visited[i] == 0 ) {
DFS( G, i, visited, circle );
}
}

return circle;
}

bool hasPathTo(multimap<int, int>& G, int v) {
int entries = G.count(v);
if (entries > 0) {
return true;
}

return false;
}

vector<int> pathTo(multimap<int, int>& G, int v) {
int entries = G.count(v);
multimap<int, int>::iterator iter = G.find(v);
vector<int> next;

while (entries--) {
next.push_back(iter->second);
}

return next;
}

void DFS(multimap<int, int>& G, int v, int* visited, bool& circle) {
visited[v] = 1; // visited[v] = 1 represents vertex v is in stack; which is equal with gray color in Intro to Alf

vector<int> next = pathTo(G, v);
for (size_t i = 0; i < next.size(); i++) {
if (visited[next[i]] == 0) {
visited[next[i]] = 1;
DFS(G, next[i], visited, circle);
} else if (visited[next[i]] == 1){
circle = false;
return;
}
}

visited[v] = 2; // visited[v] = 2 represents vertex v has been popped out of stack, which is black in Introduction of Algorithm

}
``````

};

• How do you know the number of test cases and how many yours passed?