找环
1.算法分析
1.1 判断是否存在环
如果是无向图，那么可以使用：
- 并查集判断是否存在环（并查集不仅能够判断是否存在环，还能判断是否存在奇环）
- 使用dfs打标记的方法判断是否存在环。
- tarjan缩点的方式判断是否存在双连通分量，如果存在必然存在环
- spfa判断是否存在环
如果是有向图，那么可以使用：
- dfs打标记的方法判断是否存在环
- tarjan缩点的方式判断是否存在强连通分量，如果存在必然存在环
- spfa判断是否存在环
特殊环判定：
-
奇环：并查集判定、染色法判断（是否为二分图）
-
正环、负环：spfa判断、tarjan缩点判定
1.2 找出所有环上的所有点
无向图：
- dfs打标记的方式找环，找到的是否记录pre数组，表示当前点的前一个点是哪个
- tarjan缩点后双连通分量就是多个环的并
- spfa记录pre数组打印环
有向图：
- dfs打标记的方法找环，使用pre数组记录
- tarjan缩点后强连通分量就是多个环的并
- spfa记录pre数组打印环
注意：
dfs和spfa使用pre数组找到的环，都是一个简单环
1.3 类拓扑排序找出与度数有关的点集->退化到度数为2的环
可以使用类似拓扑排序的方法找到一个点集，使得点集在任意一个点的度都大于等于k。如果k=2，那么就是一个环。
1.4 找到以s为源点的最小环
对spfa算法进行修改可以完成这个操作: O ( k m ) O(km) O(km)
1.5 floyd找到有向图/无向图的最小环
floyd+dp可以找到有向图/无向图的最小环： O ( n 3 ) O(n^3) O(n3)
2.模板
2.1 判断是否存在环
具体见 并查集、强连通分量、双连通分量、匹配问题
2.2 找出所有环上的所有点
维护pre数组，倒着找就行
2.3 类拓扑排序找出与度数有关的点集->退化到度数为2的环
见3.3
2.4 找到以s为源点的最小环
枚举版本
// spfa求最短路且找到以s为起点回到s的最小环
// 最后找到的最小环大小为dis[s]
void spfa(int s) {
queue<int> q; // 建立新队列
for (int i = 1; i <= n; ++i) {
st[i] = 0;
if (i == s) dis[i] = INF; // 初始化要求最小环的点
else {
dis[i] = mp[s][i];
st[i] = 1;
q.push(i);
}
}
while (q.size()) {
auto t = q.front();
q.pop(); // 队首元素出队
st[t] = 0; // 记录出队
for (int i = 1; i <= n; ++i) {
if (dis[i] > dis[t] + mp[t][i]) {
dis[i] = dis[t] + mp[t][i];
if (!st[i]) {
// 如果j点不在队列里
q.push(i); // 入队
st[i] = 1; // 记录
}
}
}
}
}
链式前向星版本
int spfa(int s) {
queue<int> q; // 建立新队列
for (int i = 1; i <= n; ++i) {
st[i] = 0;
if (i == s) dis[i] = INF; // 初始化要求最小环的点
else {
if (mp[s][i] == 1) dis[i] = 1, pre[i] = s; // 如果s和i点有边的话，这里记录pre数组还能够找到这个最小的环是什么
else dis[i] = INF; // 如果没有边
st[i] = 1;
q.push(i);
}
}
while (q.size()) {
auto t = q.front();
q.pop(); // 队首元素出队
st[t] = 0; // 记录出队
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (dis[j] > dis[t] + 1) {
dis[j] = dis[t] + 1;
pre[j] = t;
if (!st[j]) {
q.push(j);
st[j] = 1;
}
}
}
}
return dis[s];
}
2.5 floyd找最小环
3.典型例题
3.1 类拓扑排序找出与度数有关的点集->退化到度数为2的环
CF 1440D.Graph Subset Problem
题意： 给定一张n个点m条边的图，问是否能够找到一个点集，点集中每个点的度都大于等于k。问是否能够找到一个团&#
