C练题笔记之：Leetcode-684. 冗余连接

题目：

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

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

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

示例 1：

输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]

示例 2：

输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
 

提示:

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
edges 中无重复元素
给定的图是连通的 

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/redundant-connection
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

结果： 方法一：

 

方法二：并查集

解题思路： 方法一：

这个办法是自己想的，就是性能很低。

想法就是将所有能够相互连接的节点都用最大的那个值显示。

比如：

（1，2）（2，3）（1，3）

	1	2	3
初始化	1	2	3
（1，2）	2	2	3
（2，3）	3	3	3
（1，3）

如上图，在第一次的时候很简单1指向2，得到2，2，3. 第二次，2指向3，那么指向2的也要指向3。从而得到3，3，3 第三次可以去1和3都指向3。且这个最后一个出现的，因此这就是我们要返回的。

方法二：并查集

其实他就是不用像方法一一样将所有指向( a, b)中a的都指向b，通过find去查找。

此方法比方法一少了每次要把指向自己的重新赋值，但是多了每一次find的深度。

比如：

（1，2）（2，3）（1，3）

	1	2	3
初始化	1	2	3
（1，2）	2	2	3
（2，3）	2	3	3
（1，3）

到（1，3）的时候，1 指向2 ，2 指向3. 3指向3.。从而得到相同。
代码： 方法一：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void UpdateMap(int *map, int len, int a, int b)
{
    // map[a] == map[b] 说明已经是一样的不需要 *** 作
    if (map[a] == map[b]) {
        return;
    }
    int temp = map[a];
    // 将所有指向a的都指向b所指向的
    for (int i = 1; i < len; i++) {
        if (map[i] == temp) {
            map[i] = map[b];
        }
    }
}

int* findRedundantConnection(int** edges, int edgesSize, int* edgesColSize, int* returnSize){
    int len = edgesSize + 1;
    int *map = (int *)malloc(sizeof(int) * len);
    int *retArr = (int *)malloc(sizeof(int) * 2);
    *returnSize = 2;
    for (int i = 0; i < len; i++) {
        map[i] = i;
    }
    
    for (int i = 0; i < edgesSize; i++) {
        // 判断edges[i][0] 是否可以找到 edges[i][1]，能找到则赋值到retArr说明是多余的边
        if (map[edges[i][0]] == map[edges[i][1]]) {
            retArr[0] = edges[i][0];
            retArr[1] = edges[i][1];
        }

        // 将edges[i][0] 和 edges[i][1]的边加入
        UpdateMap(map, len, edges[i][0], edges[i][1]);
    }
    free(map);
    return retArr;
}

方法二：并查集

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int Find(int *map, int index)
{
    if (map[index] != index) {
        map[index] = Find(map, map[index]);
    }
    return map[index];
}

void UpdateMap(int *map, int a, int b)
{
    map[Find(map, a)] = Find(map, b);
}

int* findRedundantConnection(int** edges, int edgesSize, int* edgesColSize, int* returnSize){
    int len = edgesSize + 1;
    int *map = (int *)malloc(sizeof(int) * len);
    int *retArr = (int *)malloc(sizeof(int) * 2);
    *returnSize = 2;
    for (int i = 0; i < len; i++) {
        map[i] = i;
    }
    
    for (int i = 0; i < edgesSize; i++) {
        // 判断edges[i][0] 是否可以找到 edges[i][1]，能找到则赋值到retArr说明是多余的边
        if (Find(map, edges[i][0]) == Find(map, edges[i][1])) {
            retArr[0] = edges[i][0];
            retArr[1] = edges[i][1];
        }

        // 将edges[i][0] 和 edges[i][1]的边加入
        UpdateMap(map, edges[i][0], edges[i][1]);
    }
    free(map);
    return retArr;
}