How to detect cycles tideman cs50
bool is_circle (bool locked_array[MAX][MAX], int candi_count)
{
//check the basic case
//if there is only one node of course it doesn't form a circle
if (candi_count == 1)
{
return false;
}
//recursively check whether the smaller locked_array with n-1 candidate form a circle
//if the smaller one have a circle
//this mean a middle pair create a circle if added into the "locked" table
if (!is_circle(locked_array, candi_count - 1))
{
//if the one-size smaller "locked" table doesn't have a circle
//check whether adding a new candidate forms a circle
//if there is a column that is all false's after adding a new candidate
//then it must not introduce a circle in this step
for (int j = 0; j < candi_count; j++)
{
//a indicator variable for check whether a column has a true value;
bool true_in_column = false;
for (int i = 0; i < candi_count; i++)
{
if (locked_array[i][j] == true)
{
true_in_column = true;
}
}
//if there is a column doesn't have a true value then not circle is create at this step
if (true_in_column == false)
{
return false;
}
}
//if we cannot find such a column then the graph represented by current locked array
//must have a circle
return true;
}
//the smaller "locked" table forms a circle
else
{
return true;
}
}