力扣每日一题打卡 684. 冗余连接

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。

题目意思说人话就是找到一条删去后仍然联通的边。所以最简单的思路就是从后往前尝试一条条删，找到删掉之后仍然联通的边就返回。至于怎么找一个图是否联通那可太简单了，BFS，DFS，并查集啥的都可以。所以我最开始想的就是暴力用DFS去找。虽然真正写出来了才意识到这么做好像时间复杂度太高了，说不定会超时，不过写都写了就干脆写完再说。没想到交上去居然直接过了，只能说力扣的数据太水了。下面给出代码。

class Solution {
public:vector<int> findRedundantConnection(vector<vector<int>>& edges) {n = edges.size();vector<vector<bool>> ma(n + 1, vector<bool>(n + 1, false));for (auto i:edges){ma[i[0]][i[1]] = ma[i[1]][i[0]] = 1;}for (int k=n-1; k>=0; --k){vector<int> i = edges[k];ma[i[0]][i[1]] = ma[i[1]][i[0]] = 0;if (check(ma)){return i;}ma[i[0]][i[1]] = ma[i[1]][i[0]] = 1;}return edges[0];}
private:int n;bool check(vector<vector<bool>> ma){bool flag[n+1];for (int i=1; i<=n; i++) flag[i] = false;stack<int> sta;sta.push(1);flag[1] = true;while (!sta.empty()){int pt = sta.top();sta.pop();for (int i=1; i<=n; i++){if (ma[pt][i] == true){if (flag[i] == false){sta.push(i), flag[i]=true;}}}}for (int i=1; i<=n; i++){if (flag[i]==false) return false;}return true;}
};

本来我还想着超时之后就改成用邻接表去存的，按这个题的数据范围，邻接表应该是不会超时的。不过既然邻接矩阵已经过了，我也就懒得再改了。

毕竟这个题目还有更简单的方法可以实现，那就是并查集。（没学过并查集的自行百度）

思路是一条条尝试加边，判断两个点是否在同一个连通分量里面，如果在就可以直接返回这条边了，如果不在就把这条边加进去。因为题目保证只有n条边，所以这个方法找到的那条边一定是最后那条。

class Solution {
public:int find(int x){if (tree[x] != x) return find(tree[x]);return x;}void unite(int x, int y){int tx=find(x), ty=find(y);tree[tx]=ty;}vector<int> findRedundantConnection(vector<vector<int>>& edges) {const int n=edges.size();tree.clear();tree.resize(n+1);for (int i=1; i<=n; i++) tree[i]=i;for (auto i:edges){int f0=find(i[0]), f1=find(i[1]);if (f0 == f1){return i;}unite(i[0], i[1]);}return edges[0];}
private:vector<int> tree;
};

这代码甚至比用DFS还要更简洁。

因为没有进行任何优化，就连路径压缩都没做，所以这个并查集的查找时间复杂度在最坏情况下是O(n)。所以本程序的时间复杂度为O(n*n), 空间复杂度是O(n)

当然，还可以进一步使用路径压缩和按秩合并进行优化。经过优化后的并查集操作的时间复杂度是O(α(n)), α是反阿克曼函数。可以认为优化后的并查集几乎是常数时间复杂度，也就是说这题如果用优化后的并查集，时间复杂度可以看成是接近O(n)的！虽然严格来说是O(n*α(n))。优雅的并查集