检测图中环路的常用算法方法与实现
1. 并查集（Union-Find）检测环路
并查集是一种高效的数据结构，常用于动态维护集合的合并与查询操作。在无向图或有向图中判断是否存在环时，可以通过检查两个节点是否已在同一连通分量中来判定。
核心思想：当处理一条边 (u, v) 时，若发现 u 和 v 的根节点相同，则说明加入这条边会形成环。
注意：使用并查集前需确保所有涉及的节点都已初始化为其自身的父节点，尤其在节点以字符串形式给出时，应借助哈希表进行映射管理。
示例题目：ATC ABC285 D - Literal Equations
题意为判断变量间的等式关系是否自洽，可转化为图中是否有环的问题。
#include <bits/stdc++.h>
using namespace std;
unordered_map<string, string> parent;
string findRoot(string x) {
if (parent[x] != x) {
parent[x] = findRoot(parent[x]);
}
return parent[x];
}
bool solve() {
int n;
cin >> n;
bool valid = true;
for (int i = 0; i < n; ++i) {
string a, b;
cin >> a >> b;
// 初始化节点
if (!parent.count(a)) parent[a] = a;
if (!parent.count(b)) parent[b] = b;
string ra = findRoot(a);
string rb = findRoot(b);
if (ra == rb) {
valid = false; // 成环
} else {
parent[ra] = rb; // 合并集合
}
}
return valid;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << (solve() ? "Yes" : "No") << '\n';
return 0;
}
2. 拓扑排序判断有向图中是否存在环
拓扑排序适用于有向图。其基本原理是基于入度进行节点排序：每次取出入度为0的节点，并将其邻居的入度减一。如果最终能访问所有节点，则图无环；否则存在环。
关键点：环内的节点由于相互依赖，永远无法被消去入度至0，因此不会进入队列。
算法流程：
- 统计每个节点的入度。
- 将所有入度为0的节点加入队列。
- 依次出队并更新邻接节点的入度。
- 若最后出队节点数等于总节点数，则无环；否则存在环。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
vector<int> graph[MAXN];
int indegree[MAXN];
int topo[MAXN], idx = 0;
bool isDAG(int n) {
queue<int> q;
idx = 0;
// 入度为0的节点入队
for (int i = 1; i <= n; ++i) {
if (indegree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int u = q.front(); q.pop();
topo[idx++] = u;
for (int v : graph[u]) {
if (--indegree[v] == 0) {
q.push(v);
}
}
}
return idx == n; // 是否所有节点都被处理
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
indegree[v]++;
}
if (isDAG(n)) {
for (int i = 0; i < n; ++i) {
cout << topo[i] << " ";
}
cout << "\n";
} else {
cout << "-1\n"; // 存在环
}
return 0;
}
该方法时间复杂度为 O(n + m)，适合稀疏图和任务调度类问题中的依赖检测。
