力扣每日一题打卡 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))。优雅的并查集