Detect Cycle in a Directed Graph
推断一个图是否有环，有环图例如以下：
这里唯一注意的就是，这是个有向图， 边组成一个环，不一定成环，由于方向能够不一致。
这里就是添加一个数组保存当前已经訪问过的路径信息 recStack[]；
而visited[]数组是訪问过的点的信息，两者作用是不一样的。
知道这个知识点，这道题就非常easy了。
原文：
http://www.geeksforgeeks.org/detect-cycle-in-a-graph/
#include <stdio.h>
#include <list>
#include <limits.h>
#include <iostream>
using namespace std; class DetectCycleinaDirectedGraph
{
int size;
list<int> *adj; bool isCycleUtil(int v, bool visited[], bool *recStack)
{
if (!visited[v])
{
//本题巧妙之处：额外添加recStack,because it is directed, if it is undirected, then we don't really need recStack.
visited[v] = recStack[v] = true;
list<int>::iterator it = adj[v].begin();
for ( ; it != adj[v].end(); it++)
{
if (!visited[*it] && isCycleUtil(*it, visited, recStack))
return true;
else if (recStack[*it]) return true;
}
recStack[v] = false;
}
return false;
}
public:
DetectCycleinaDirectedGraph(int v) : size(v)
{
adj = new list<int>[size];
} void addEdge(int v, int w)
{
adj[v].push_back(w);
} bool isCyclic()
{
bool *visited = new bool[size];
bool *recStack = new bool[size];
fill(visited, visited+size, false);
fill(recStack, recStack+size, false); for (int i = 0; i < size; i++)
{
if (isCycleUtil(i, visited, recStack)) return true;
}
return false;
}
}; void DetectCycleinaDirectedGraph_RUN()
{
DetectCycleinaDirectedGraph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3); if(g.isCyclic())
cout << "Graph contains cycle\n";
else
cout << "Graph doesn't contain cycle\n";
}