转载自：https://blog.csdn.net/dfq12345/article/details/78004876
进行深度优先遍历的时候，当考察的点的下一个邻接点是已经被遍历的点，并且不是自己之前的父亲节点的时候，我们就找到了一条逆向边，因此可以判断该无向图中存在环路。
visited数组记录了节点的访问状态，visited[i] = 0表示节点i尚未被访问过; visited[i] = 1表示节点i被访问了，但是尚未被检测完毕; visited[i] = 2表示节点i已经被检测完毕了，对于检测完毕了的节点，其所有的临边都已经被考虑过了，如果存在逆向边的话已经被检测了，从而避免了重复地进行检测。 father[i]表示到达节点i经过的前驱节点，通过反向索引father数组，我们可以找出这个环。
#include <stdio.h> #include <stdlib.h>int * newIntRaw(int n) {return (int *)malloc(sizeof(int) * n); }
int * newInt(int n, int init) {int *p = newIntRaw(n);int i;for (i = 0; i < n; ++i)p[i] = init;return p; }
int ** newMap(int n, int m, int init) {int **res = (int **)malloc(sizeof(int *) * n);int i;for (i = 0; i < n; ++i)res[i] = newInt(m, init);return res; }typedef struct {int e;int n;int **map; } Graph;Graph * newGraph() {int n, e;int i;int from, to;Graph *g = (Graph *)malloc(sizeof(Graph));scanf("%d %d", &n, &e);g->n = n;g->e = e;g->map = newMap(n, n, 0);for (i = 0; i < e; ++i) {scanf("%d %d", &from, &to);g->map[from][to] = 1;g->map[to][from] = 1;}return g; }void dispGraph(Graph *g) {int i, j;for (i = 0; i < g->n; ++i) {printf("%d: ", i);for (j = 0; j < g->n; ++j) {if (g->map[i][j] == 1)printf("%d ", j);}printf("\n");} }// ---------------------------solve----------------------- int *visited; int *father;void dfs(Graph *g, int s) {int i;visited[s] = 1;for (i = 0; i < g->n; ++i) {if (g->map[s][i] == 1) {if (visited[i] == 0) {father[i] = s;dfs(g, i);}else if (visited[i] == 1 && i != father[s]) {int tmp = s;printf("find a ring: %d --> ", i);while (tmp != i) {printf("%d --> ", tmp);tmp = father[tmp];}printf("%d\n", tmp);}}}visited[s] = 2; // 避免重复计算环 }void findRing(Graph *g) { // dispGraph(g);int i;visited = newInt(g->n, 0);father = newInt(g->n, -1);for (i = 0; i < g->n; ++i)if (visited[i] == 0)dfs(g, i); }int main() {Graph *g = newGraph();findRing(g);return 0; }/* 5 6 0 1 0 4 4 3 3 1 1 2 3 2 */
