当前位置：首页 > article >正文

LeetCode每日一题685---冗余连接 II

article 2024/11/2 10:51:18

一、题目描述

在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。

输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges 。每个元素是一对 [ui, vi]，用以表示有向图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。

返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

示例 1：
在这里插入图片描述

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

示例 2：
在这里插入图片描述

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

提示：
n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ui, vi <= n

二、解题思路

这道题目与冗余连接 I一样需要用到并查集，但是要分三种情况：

情况一：入度为2，部分成环
情况二：入度为2，不成环
情况三：入度全为1，只能成环

对于情况一和情况二，一定是删除指向入度为2的节点的两条边其中的一条，如果删了一条，判断这个图是一个树，那么这条边就是答案，同时注意要从后向前遍历，因为如果两天边删哪一条都可以成为树，就删最后那一条。
在这里插入图片描述

对于情况三，明确没有入度为2的情况，那么一定有向环，找到构成环的边就是要删除的边。
在这里插入图片描述

三、代码

// 并查集找父结点
 int find(int parent[],int x){
    if(x == parent[x]){
        return x;
    }else{
        parent[x] = find(parent,parent[x]);
        return parent[x];
    }
 }

// 对于情况一和情况二判断要删除那条边
bool isTreeAfterRemoveEdge(int** edges,int edgeSize,int deleteEdge){

    //初始化并查集
    int parent[edgeSize+1];
    for(int i=0;i<=edgeSize;i++){
        parent[i] = i;
    }
    int root1,root2;
    for(int i=0;i<edgeSize;i++){
        if (i == deleteEdge) continue;  // 跳过要删除的边
        root1 = find(parent,edges[i][0]);
        root2 = find(parent,edges[i][1]);
        if(root1 == root2){
            return false;
        }

        parent[root1] = root2;
    }
    
    return true;
}

//  情况三，找到构成环的边就是要删除的边。
int  getRemoveEdge(int** edges,int edgeSize){
     //初始化并查集
    int parent[edgeSize+1];
    for(int i=0;i<=edgeSize;i++){
        parent[i] = i;
    }
     int root1,root2;
     for(int i=0;i<edgeSize;i++){
        root1 = find(parent,edges[i][0]);
        root2 = find(parent,edges[i][1]);
        if(root1 == root2){
            return i;
        }
        parent[root1] = root2;
     }

     return -1;


}

int* findRedundantDirectedConnection(int** edges, int edgesSize, int* edgesColSize, int* returnSize) {

    // 计算每一个结点的入度
    int inDefree[1010]={0};
    *returnSize = 2;
    
    for(int i=0;i<edgesSize;i++){
        inDefree[edges[i][1]]++;
    }
    //   记录入度为2的边（如果有的话就两条边）
    // 找入度为2的节点所对应的边，注意要倒序，因为优先返回最后出现在二维数组中的答案
    int *array = (int *)malloc(sizeof(int) *2);
    int k=0;
    for(int i = edgesSize-1;i>=0;i--){
        if(inDefree[edges[i][1]]==2){
            array[k++] = i;
        }
    }

     // 如果有入度为2的节点，那么一定是两条边里删一个，看删哪个可以构成树
     if(k>0){
        if(isTreeAfterRemoveEdge(edges,edgesSize, array[0])){
            return edges[array[0]];
        }else{
            return edges[array[1]];
        }
     }


     // 明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了

     int res = getRemoveEdge(edges,edgesSize);

     return edges[res];
    
}