【Day 21】Algorithm - Find Cycle in Directed Graph

这题真的需要花一点功夫，题目并不难懂，但是不能用直观的方式去写，可以上网搜寻关键字「find cycle in directed graph」，以及前一篇所提到的「depth-first search」(DFS)。

题目

输入输出格式

Sol.
我采用的作法会先将题目给的资讯整理成阵列：

1. 依题目建 adjacency matrix
2. 建一个阵列(selectArray)存哪些点需要判断是否有回圈 (若题目给定1、2、3、4，点1、2、4有回圈也算是有回圈)
3. 建三个阵列，分别是whiteSet、graySet、blackSet：
   whiteSet：还没判断过的点
   graySet：正在判断或已判断的点
   blackSet：不用再判断的点，有可能是因为没有与其连接的点，或其所连接的点不属於需要判断的点
   各 set 的长度皆为输入测资第一行中 node 的数量，以 0 表示此点不在这个 set 中，反之，1 表示此点在这个 set。因此，同一个点指有可能在任一个 set 中表示 1，因为不会同时并存於两个或以上的 set。
   这个方法大家可以参考Tushar Roy的 Detect Cycle in Directed Graph Algorithm
4. 建pathArray，长度为总 node 数量，并将阵列中各项初始化为 -1，存目前已经过的点

Pseudocode

建 adjacencyMatrix、selectArray
建 whiteSet、graySet、blackSet
若是没有要判断是否有回圈的点就先放入blackSet，其余在whiteSet中皆表示1
建 pathArray

int path = 0;	// 接下来这个点要放在 pathArray 中的哪
bool cycle = false;	// 是否有回圈
bool neighbor = false;	// 有没有与之连接的点
int i = 0;	// 现在判断到第几个点

//	开始判断
While (cycle == false或i>= pointQ)
	
	如果根本就不够判断是否有回圈就直接 break
	
	// 判断这个点有没有在blackSet中
    bool blackFlag = true;
    if遍历完blackFlag还是true代表不用再判断，这时就break
	
	// 不用判断这个点就跳过继续判断下一个点
	if (blackSet[i] == 1)
		i++ 并continue
	
	// 如果这个点可以拿来判断
	if (whiteSet[i] == 1 && graySet[i] == 0)
		whiteSet[i] = 0;
		graySet[i] = 1;
		pathArray[path] = i;
		path++;
	
	// 找有没有与之相邻的 (这个方法真的太聪明..一定要好好学起来)
	for u in range 0～nodes总数
		neighbor = false;
		// 把所有没有neighbor的情形都判断完後neighbor 就会是true
		neighbor = true;
		if 第u个点是在whiteSet中
			whiteSet[u] = 0;
			graySet[u] = 1;
			pathArray[path] = u;
			path++;
			i = u;
		else if 第u个点是在graySet中
			cycle = true;
		break;
	
	// 若没有点与之相邻了就代表这个点没用了，把他放到 blackSet
	if neighbor == false
		whiteSet[i]、graySet[i] = 0
		blackSet[i] = 1
		//	在pathArray中删除这格
		path--;
		pathArray[path] = -1;
		
		让 i 回到pathArray中最後一个不为 -1 的点
	
最後输出cycle