前言
这题用鸡毛并查集啊,直接 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];}
};
结果
作者能力有限,如有问题请多多指教!