leetcode 684 冗余连接题解

2024/10/28 11:10:24 来源：https://blog.csdn.net/ZXTpower/article/details/143272027 浏览: 次关键词：leetcode 684 冗余连接题解

前言

这题用鸡毛并查集啊，直接 tarjan 求割边呗，为了水这篇题解，我还专门写了个 tarjan 的博客，嘿嘿。
tarjan 求割点和割边

题解

当你求出来所有的割边之后，你就从后往前遍历所有的边，然后一个遇到的不是割边的边就是答案。

代码

const int maxn = 1005;class Solution {
public:int head[maxn], tot;Solution(){for (int i = 1; i <= 1000; i++)head[i] = 0;tot = 1;}struct edge{int to, nxt;}e[maxn * 2];void addedge(int u, int v){e[++tot].nxt = head[u];e[tot].to = v;head[u] = tot;}vector<int> findRedundantConnection(vector<vector<int>>& edges) {int N = edges.size();vector<int> vis(N + 10, 0), low(N + 10, 0), dfn(N + 10, 0);for (int i = 0; i < edges.size(); i++){int u = edges[i][0], v = edges[i][1];addedge(u, v); addedge(v, u);}int cnt = 0;auto tarjan = [&](auto&& tarjan, int x, int index_edge) -> void {low[x] = dfn[x] = ++cnt;for (int i = head[x]; i; i = e[i].nxt){int v = e[i].to;if (!dfn[v]){tarjan(tarjan, v, i);low[x] = min(low[v], low[x]);if (low[v] > dfn[x])vis[i / 2 - 1] = 1; }elseif (i != (index_edge ^ 1))low[x] = min(low[x], dfn[v]);}};tarjan(tarjan, 1, 1);for (int i = N - 1; i >= 0; i--)if (!vis[i])return edges[i];return edges[0];}
};