树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 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))。优雅的并查集