# Graph using bitmap

• ``````#define set(map,x) \
((map)[(x) >> 5] |= (1 << ((x) & 0x1F)))

#define test(map,x) \
((map)[(x) >> 5] & (1 << ((x) & 0x1F)))

bool hasCircle(int **g, int *courses, int numCourses, int curr){
// courses[curr] is been visiting by children , set it = 1
courses[curr] = 1;
for (int i = 0; i < numCourses; ++i){
if (!test(g[curr], i)) continue;
else{
if (courses[i] == 1) // circle
return true;
if (hasCircle(g, courses, numCourses, i))
return true;
}
}
courses[curr] = -1; // all curr's children has been visited
return false;
}

bool canFinish(int n, int** pre, int preRow, int preCol) {
if (n <0 || preRow <0  || preCol<0) return 0;
if (n == 0) return 0;
if (n >= 1 && preRow == 0 && preCol == 0) return 1;
int **g = malloc(sizeof(int *)* n);
int gcol = (n + 31) / 32;
int grow = n;
for (int i = 0; i < grow; ++i){
g[i] = malloc(sizeof(int)* gcol);
memset(g[i],0,sizeof(int) * gcol);
}

for (int i = 0; i < preRow; ++i){
int a = pre[i][0];
int b = pre[i][1];
set(g[a], b);
}

// graph complete

// dfs to detects circle

int *courses = malloc(sizeof(int)* n);
memset(courses,0,sizeof(int) * n);

int curr;
for(int i = 0; i < n; ++i){
if(courses[i] == 0)
if(hasCircle(g, courses, n, i))
return false;
}

return true;
}``````

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