1. 有向图找环
HDOJ 3342 Legal or Not https://acm.hdu.edu.cn/showproblem.php?pid=3342
题意：
给一个 \(N\) 个点 \(N\) 条边的有向图，第 \(i(1 \leq M)\) 条边从 \(a_i\) 连向 \(b_i\) ，询问该图是否无环。
\(2 \leq N, M \leq 100, 0 \leq a_i, b_i \leq N - 1\)
题解：
建图然后使用 Toposort ，如果没有剩余的图，则整个图无环。否则剩余的图是一个环。
std::vector<std::vector<int> > adj(N + 1);
std::vector<int> ind(N + 1);
for (int i = 1; i <= M; i++) {
int u, v; std::cin >> u >> v;
u++; v++;
adj[u].push_back(v);
ind[v]++;
}
std::queue<int> que;
for (int i = 1; i <= N; i++) if (ind[i] == 0) que.push(i);
std::queue<int> S;
while (!que.empty()) {
int x = que.front();
que.pop();
S.push(x);
for (auto y : adj[x]) {
if (--ind[y] == 0)
que.push(y);
}
}
std::cout << (S.size() == N ? "YES" : "NO") << "\n";
时间复杂度 \(O(N + M)\) 。
HDU 1325 Is It A Tree? https://acm.hdu.edu.cn/showproblem.php?pid=1325
题意：
给一个有向图，判断是否是一棵树。
题解：
先用并查集判断是否图是连通图。
然后若整个图有且仅有一个节点的入度为 0 ，其他节点的入度为 1 。则是一棵树。
时间复杂度 \(O(N + M)\) 。
2. 无向图找环
http://poj.org/problem?id=3895
3. 最小环
有向图最小环：
无向图最小环：
暴力：
Dijikstra：
Floyd：
HDOJ 1599 https://acm.hdu.edu.cn/showproblem.php?pid=1599
HDOJ 6005 https://acm.hdu.edu.cn/showproblem.php?pid=6005
POJ 1734 http://poj.org/problem?id=1734
4. 正环/负环
正环即反权图上找负环。负环跑 Bellman-ford 迭代轮数 \(\geq N\) 。
https://www.luogu.com.cn/problem/P3385
题意：
给一个 \(n\) 个点 \(m\) 条边的有向图。询问是否存在从 \(1\) 出发能到达的负环。
\(1 \leq n \leq 2 \times 10^{3}, 1 \leq m \leq 3 \times 10^{3}, 1 \leq u, v \leq n, -10^{4} \leq w \leq 10^{4}, 1 \leq T \leq 10\)
题解：
从 \(1\) 跑 Bellman-ford 的第 \(N\) 轮，如果依然有边可以被松弛，则从 \(1\) 出发存在负环。
一轮就可以拿出负环的证明：
负环被确定后。每个点到源点的距离一定小于上一轮的距离。否则这个点不在负环上。
int n, m; std::cin >> n >> m;
std::vector<std::array<int, 3> > E;
for (int i = 1; i <= m; i++) {
int u, v, w; std::cin >> u >> v >> w;
if (w >= 0) {
E.push_back({u, v, w});
E.push_back({v, u, w});
} else {
E.push_back({u, v, w});
}
}
int M = E.size();
std::vector<ll> dis(n + 1, llinf);
dis[1] = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < M; j++) {
int u = E[j][0], v = E[j][1], w = E[j][2];
if (dis[u] == llinf) continue;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
}
}
}
std::vector<int> negative(n + 1);
for (int j = 0; j < M; j++) {
int u = E[j][0], v = E[j][1], w = E[j][2];
if (dis[u] == llinf) continue;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
negative[v] = 1;
}
}
int ok = 0;
for (int i = 1; i <= n; i++) ok |= negative[i] > 0;
std::cout << (ok ? "YES" : "NO") << "\n";
时间复杂度 \(O(nm)\) 。
5. DAG 最长路
P1807 最长路 https://www.luogu.com.cn/problem/P1807
题意：
给一个有向无环带权图，询问节点 \(1\) 到节点 \(n\) 的最长距离。
\(1 \leq n \leq 1500, 1 \leq m \leq 5 \times 10^{4}, 1 \leq u, v \leq n, -10^{5} \leq w \leq 10^{5}\)
题解：
先 \(O(n + m)\) 对 DAG 的反权图 TopoSort ，然后在 Topo 序上完成最短路的松弛操作。
结果的负数即最长路。
int n, m; std::cin >> n >> m;
std::vector<std::vector<std::array<int, 2> > > adj(n + 1);
std::vector<int> ind(n + 1);
for (int i = 1; i <= m; i++) {
int u, v, w; std::cin >> u >> v >> w;
adj[u].push_back({v, -w});
ind[v]++;
}
std::queue<int> S, L;
for (int i = 1; i <= n; i++) if (ind[i] == 0) S.push(i);
while(!S.empty()) {
int x = S.front();
S.pop();
L.push(x);
for (auto info : adj[x]) {
int y = info[0];
if (!--ind[y])
S.push(y);
}
}
std::vector<ll> dp(n + 1, llinf);
dp[1] = 0;
while (!L.empty()) {
int u = L.front();
L.pop();
if (dp[u] == llinf) continue;
for (auto info : adj[u]) {
int v = info[0], w = info[1];
dp[v] = std::min(dp[v], dp[u] + w);
}
}
std::cout << (dp[n] == llinf ? -1 : -dp[n]) << "\n";
时间复杂度 \(O(n + m)\) 。
6. 非 DAG 最长路
反权图上跑 Bellman-ford 。
https://atcoder.jp/contests/abc061/tasks/abc061_d
题意：
给一个一般图，询问 1 到 n 的最长路。
如果没有负环，从 1 跑反权图的 Bellman-ford 。
如果 1 在一个负环内，拿出这个负环。
基于这个负环，迭代出负环可达的点，若可达 n 。则最长路无限长。
int N, M; std::cin >> N >> M;
std::vector<std::array<int, 3> > E(M + 1);
for (int i = 1; i <= M; i++) {
int u, v, c; std::cin >> u >> v >> c;
E[i] = {u, v, c};
}
std::vector<std::array<int, 3> > anti_E(E.begin(), E.end());
for (int i = 1; i <= M; i++) anti_E[i][2] *= -1;
std::vector<ll> dist(N + 1, llinf);
dist[1] = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
int u = anti_E[j][0], v = anti_E[j][1], c = anti_E[j][2];
if (dist[u] == llinf) continue;
if (dist[u] + c < dist[v]) {
dist[v] = dist[u] + c;
}
}
}
std::vector<int> negative(N + 1);
std::vector<int> can(N + 1);
for (int j = 1; j <= M; j++) {
int u = anti_E[j][0], v = anti_E[j][1], c = anti_E[j][2];
if (dist[u] == llinf) continue;
if (dist[u] + c < dist[v])
negative[v] = can[v] = 1;
}
for (int i = 1; i <= N - 1; i++) {
for (int j = 1; j <= M; j++) {
int u = anti_E[j][0], v = anti_E[j][1], c = anti_E[j][2];
if (dist[u] == llinf) continue;
if (can[u])
can[v] = 1;
}
}
if (can[N]) std::cout << "inf\n";
else std::cout << -dist[N] << "\n";