本题需要在图中找到一个长度大于给定值 k 的环。

 

思路：

 先将所有边存下来，画出图，再DFS找环，找到一个就计算它的长度，若长度满足条件，则跳出，否则继续。存图要用邻接表，矩阵会超内存。

 

DFS找环的方法：

 

 首先要知道几个DFS中的概念：

 在图的遍历中，往往设置了一个标记数组vis的bool值来记录顶点是否被访问过。但有些时候需要改变vis值的意义。令vis具有3种值并表示3种不同含义

  1. vis = 0,表示该顶点没没有被访问
  2. vis = 1,表示该顶点已经被访问，但其子孙后代还没被访问完，也就没从该点返回
  3. vis = 2,，表示该顶点已经被访问，其子孙后代也已经访问完，也已经从该顶点返回

 vis的3种值表示的是一种顺序关系和时间关系

 

DFS过程中，对于一条边u->v

  1. vis[v] = 0,说明v还没被访问，v是首次被发现，u->v是一条树边
  2. vis[v] = 1,说明v已经被访问，但其子孙后代还没有被访问完（正在访问中），而u又指向v？说明u就是v的子孙后代，u->v是一条后向边，因此后向边又称返祖边
  3. vis[v] = 3,z说明v已经被访问，其子孙后代也已经全部访问完，u->v这条边可能是一条横叉边，或者前向边

在很多算法中，后向边都是有作用的，但是前向边和横叉边的作用往往被淡化，其实它们没有太大作用。

 

1

 

总的来说：

  • 前向边指从点A到点B，其中B不是A的祖宗节点。

  • 后向边指从点A到点B，其中B是A的祖宗节点。

 

通常使用后向边找环。

 

对图中任意节点开始访问，若访问其子孙节点的过程中，出现访问到的点vis=1，即该点正在被访问，说明该点是当前点的祖宗节点，即出现了后向边，此时就出现了环。

 

若要输出环的路径，则对建立一个father数组，存每个点的父节点，访问过程中同时完善father数组；若发现后向边，则沿father数组向上找。

 

本题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <stdio.h>
#include <stdlib.h>
#include<vector>
const int maxn = 1e6;

int * newIntRaw(int n)
{
	return (int *)malloc(sizeof(int) * n);
}
int * newInt(int n, int init)
{
	int *p = newIntRaw(n+1);
	int i;
	for (i = 0; i <= n; ++i)
		p[i] = init;
	return p;
}

struct Node {
	std::vector<int>to;
}nd[maxn];
typedef struct
{
	int e;
	int n;
} Graph;

Graph * newGraph()
{
	int n, e;
	int i;
	int u,v;
	Graph *g = (Graph *)malloc(sizeof(Graph));
	scanf("%d %d %d", &n, &e, &k);
	g->n = n;
	g->e = e;
	for (i = 0; i < e; ++i) {
		scanf("%d %d", &u, &v);
		nd[u].to.push_back(v);
		nd[v].to.push_back(u);
	}
	return g;
}


// ---------------------------solve-----------------------
int *visited;
int *father;
int len;
int k;
bool ok=0;
void dfs(Graph *g, int s)
{
	if (ok)return;
	visited[s] = 1;
	for (auto i:nd[s].to) {
		if (ok)break;
		if (visited[i] == 0) {
			father[i] = s;
			dfs(g, i);
		}
		else if (visited[i] == 1 && i != father[s]) {
			std::vector<int>vc;
			int tmp = s;
			vc.push_back(i);
			len = 1;
			while (tmp != i) {
				len++;
				vc.push_back(tmp);
				tmp = father[tmp];
			}
			if (len > k&&!ok) {
				ok = 1;
				printf("%d\n", len);
				for (auto c : vc)
					printf("%d ", c);
				printf("\n");
			}
		}
	}
	visited[s] = 2; // 避免重复计算环
}

void findRing(Graph *g)
{
	int i;
	visited = newInt(g->n, 0);
	father = newInt(g->n, -1);
	for (i = 0; i < g->n; ++i)
		if (ok)return;
		if (visited[i] == 0)
			dfs(g, i);
}

int main()
{
	Graph *g = newGraph();
	findRing(g);
	return 0;
}