Leetcode - 685：冗余连接

树树树树树树树树树树树…

684.冗余连接

在本问题中, 树指的是一个连通且无环的无向图。

输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。

返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。

示例 1：

输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的无向图为:
1
/ \
2 - 3
示例 2：

输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
解释: 给定的无向图为:
5 - 1 - 2
| |
4 - 3
注意:

输入的二维数组大小在 3 到 1000。
二维数组中的整数在1到N之间，其中N是输入数组的大小。
更新(2017-09-26):
我们已经重新检查了问题描述及测试用例，明确图是无向 图。对于有向图详见冗余连接II。对于造成任何不便，我们深感歉意。

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

图有的时候是树，树无时无刻是图

解法：并查集

由于本题所给的是无向图，故不需要考虑边的方向

考虑并查集算法：将所有联通的点都纳入数个集合中以方便查找：

• 初始化每个点为一个自身的集合
• 逐条边读入，分别查找两端点所属集合
• 两点所属集合不同则合并两集合，否则返回该条边即可

初版代码

一开始我是这么写的：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int set[10000][10000]={0};//第一维分配给每一个点，第二维作为该点的集合保存其他附庸点
int set_size[10000][2]={0};//0表示所属集合，1表示集合中点的数量

int find_x(int src)
{
    return set_size[src][0] == src ? src : find_x(set_size[src][0]);
}

void union_set(int s1, int s2)
{    
    while(set_size[s1][0]!=s1)
        s1 = set_size[s1][0];
    while(set_size[s2][0]!=s2)
        s2 = set_size[s2][0];
    for(int i=0;i<=set_size[s2][1];i++)
    {
        set_size[s1][1]++;
        set[s1][set_size[s1][1]] = set[s2][i];
    }
    set_size[s2][0] = s1;
}

int* findRedundantConnection(int** edges, int edgesSize, int* edgesColSize, int* returnSize)
{    
    *returnSize = 2;
    int *ret = malloc(sizeof(long long int) * 2);
    ret[0] = 0;
    ret[1] = 0;
    
    for(int i=1;i<=edgesSize;i++)
    {
        set_size[i][0] = set[i][0] = i;
        set_size[i][1] = 1;
    }

    int start, end;
    int flag1,flag2;
    for(int i=0;i<edgesSize;i++)
    {
        start = edges[i][0];
        end = edges[i][1];
        flag1 = find_x(start);
        flag2 = find_x(end);
        if(flag1 == flag2)
        {
            ret[0] = start;
            ret[1] = end;
            return ret;
        }
        union_set(start,end);
    }
    return ret;
}

由于一开始我们就初始化一个较大的二维数组，故空间复杂度上比较吃亏

优化：减少冗余步骤与空间

我们尝试改变之前一拍脑门时繁复冗杂的写法，在归并时仅记录长度进行归并即可（即小集合归并到大集合），并使用动态数组以尽量减少空间使用

思路还是合之前的一样，构造代码如下：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int *set;
int *set_size;

int find_x(int src)
{
    return set[src] == src ? src : find_x(set[src]);
}

void union_set(int s1, int s2)
{    
    s1 = find_x(s1);
    s2 = find_x(s2);
    if(set_size[s1]<set_size[s2])
    {
        set_size[s2] += set_size[s1];
        set[s1] = set[s2];
    }
    else
    {
        set_size[s1] += set_size[s2];
        set[s2] = set[s1];
    }
}

int* findRedundantConnection(int** edges, int edgesSize, int* edgesColSize, int* returnSize)
{    
    *returnSize = 2;
    int *ret = malloc(sizeof(int) * 2);
    set = (int*)malloc(sizeof(int)*(edgesSize+5));
    set_size = (int*)malloc(sizeof(int)*(edgesSize+5));
    ret[0] = 0;
    ret[1] = 0;
    
    for(int i=1;i<=edgesSize;i++)
    {
        set[i] = i;
        set_size[i] = 1;
    }

    int start, end;
    int flag1,flag2;
    for(int i=0;i<edgesSize;i++)
    {
        start = edges[i][0];
        end = edges[i][1];
        flag1 = find_x(start);
        flag2 = find_x(end);
        if(flag1 == flag2)
        {
            ret[0] = start;
            ret[1] = end;
            return ret;
        }
        union_set(start,end);
    }
    return ret;
}

（减少差不多一半空间，但是看起来并没有什么用…）