Leetcode
12 minutes read (About 1864 words) 0 visits

Leetcode 685. Redundant Connection II

题目

685. Redundant Connection II

  • Difficulty: Hard
  • Total Accepted: 11.2K
  • Total Submissions: 39.7K

In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, …, N), with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] that represents a directed edge connecting nodes u and v, where u is a parent of child v.

Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.

Example 1:

Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given directed graph will be like this:
  1
 / \
v   v
2-->3

Example 2:

Input: [[1,2], [2,3], [3,4], [4,1], [1,5]]
Output: [4,1]
Explanation: The given directed graph will be like this:
5 <- 1 -> 2
     ^    |
     |    v
     4 <- 3

Note:

  • The size of the input 2D-array will be between 3 and 1000.
  • Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

解题报告

AC 截图

题目大意

该问题给出一组有向图内的边，并且给出等同数量的节点，构成一个可以通过 删掉一条边 而成为 有根树 的有向图。在有多个答案时，输出最后出现的可用边。

解题思路

该题乍一看情况非常复杂，因为要从一个有向图转换为有根树，需要消除图中所有的回环，以及所有入度大于 1 的节点（后称「双源」节点）。但是冷静下来想想，题目其实已经给出了相当优厚的条件——只能删掉一条边。

根据这个条件，我们可以反推回输入数据的情况：该有向图只可能是下列三种情况的一种。

  • 有一个回环，没有「双源」节点
  • 有一个「双源」节点，没有回环
  • 有一个「双源」节点，并且该节点也在一个回环内

考虑第一种情况，因为只删掉一条边就可以构成有根树，那么最后形成环的那条边，肯定就是我们要找的边，因而在扫描一边所有边的时候监控整个图的连通性即可，一旦发现成环，我们就删掉那条边。

考虑第二种情况，在没有回环的情况下，两条边可以 任意地删除，因而删除触发形成双源节点条件的边即可，因其相对位于集合的后部，处理方式同第一种。

考虑第三种情况，因为这个时候双源节点接入的两条边中有一条会参与成环，因而要同时解除成环和双源，我们只能 删掉参与成环和双源节点的唯一边。同时，为了保证不会漏掉这种重叠情况，在前两种情况的判定中，我们 不能在判定后立刻作出相应操作，而要等待整个边集合扫描完后再处理。

那么接下来，我们来考虑如何判定双源与回环的问题。

（这实际上是一个简化的 并查集 问题，有兴趣的同学可以了解一下）我们维护一个「祖先」数组，它标定整个图中每个节点的祖先。每当一条边由点 A 指向点 B 时，我们令点 B 的祖先为点 A 的祖先。这样，当一条边指向一个有祖先的节点时，就会发生「双源」；当一条边的两端祖先相同时，就会发生「回环」。

必须要考虑的是，当「双源」发生时，对双源节点的祖先查找可能引导向两个结果，如何对两个结果进行处理会是一个问题。

题解 1

结果截图

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
static const auto runfirst = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
  int parent1, parent2;
  int subParent1, subParent2;
  vector<int> *doubleSourceEdge, *circularEdge;
  int doubleSourceNode;
  int subParent;
  int sameParent;

  vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
    int size = edges.size();
    int *parent = new int[size + 1];
    int *father = new int[size + 1];

    doubleSourceEdge = circularEdge = nullptr;
    doubleSourceNode = subParent = 0;
      
    memset(parent, 0, (size + 1) * sizeof(int));

    for (auto &iter : edges) {
      if (doubleSourceNode) {
        auto temp1 = findParentFork(parent, father, iter[0]),
          temp2 = findParentFork(parent, father, iter[1]);
        
        parent1 = temp1[0];
        parent2 = temp2[0];

        subParent1 = temp1[1];
        subParent2 = temp2[1];
      }
      else {
        parent1 = findParent(parent, iter[0]);
        parent2 = findParent(parent, iter[1]);
      }

      if (parent[iter[1]]) {
        // Double source
        if (parent1 == parent2) {
          return iter;
        }

        if (circularEdge) {
          return vector<int>({father[iter[1]], iter[1]});
        }
        else {
          doubleSourceNode = iter[1];
          doubleSourceEdge = new vector<int>({father[iter[1]], iter[1]});
        }

        subParent = parent2;
      }

      if (doubleSourceNode) {
        if ((sameParent = parent1) == parent2 || (sameParent = parent1) == subParent2 || (sameParent = parent2) == subParent1) {
          if (findParent(parent, doubleSourceNode) == sameParent) {
            return vector<int>({father[doubleSourceNode], doubleSourceNode});
          }
          else {
            return *doubleSourceEdge;
          }
        } 
      }
      else if (parent1 == parent2) {
        // Circular path
        circularEdge = new vector<int>({iter[0], iter[1]});
      }

      parent[iter[1]] = parent1;
      father[iter[1]] = iter[0];
    }

    if (doubleSourceNode) {
      return vector<int>({father[doubleSourceNode], doubleSourceNode});
    }
    else {
      return *circularEdge;
    }
  }

  int findParent(int *parent, int index) {
    if (index == parent[index] || parent[index] == 0)
      return index;
    else 
      return findParent(parent, parent[index]);
  }

  vector<int> findParentFork(int *parent, int *father, int index) {
    if (index == parent[index] || parent[index] == 0)
      return vector<int>({index, 0});
    else {
      if (index == doubleSourceNode) return vector<int>({findParent(parent, father[index]),
        findParent(parent, subParent)});
      else return findParentFork(parent, father, father[index]);
    }
  }
};

改进思路

在题解 1 中，我们通过在一次扫描中监控前两种情况来达成要求。在检测到其中一种情况发生后，我们将继续扫描，直到第三种情况发生或者到达终点。这个算法很好的达到了我们的预期效果，但是有很多问题。

首先，在触发「双源」后，后续扫描复杂度陡增，严重影响了程序运行效率。其次，过于复杂的逻辑判断大大增加了编程难度。最后，在“寻找祖先”的过程中，大量可以复用的信息被浪费掉。

那么有没有什么优化的办法呢？

首先，我们考虑一下这三种情况。实际上我们不必在扫描时判断如此多的内容。首先，我们进行一次扫描，查看是否有「双源」的发生。若有，我们去除触发双源的边，再进行一次查找，此时如果没有回环的发生，那么这条边就是目标边，否则，就说明是另一条「双源」边在回环内，那条边也就是目标边。如果没有发生「双源」，则是简单的回环问题，找到成环边即可。

然后，我们考虑一下信息复用的问题。由动态规划的思想，我们可以在每次寻找祖先的过程中，更新整个路径上的所有祖先，从而大大减少后续的查找祖先的时间。

具体实现见题解 2。

题解 2（最优解）

结果截图

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
static int fast = []() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  return 0;
}();

class Solution {
public:
  int parent1, parent2;
  vector<int> doubleSourceEdge1, doubleSourceEdge2;

  vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
    int size = edges.size();
    int *father = new int[size + 1];

    doubleSourceEdge1 = doubleSourceEdge2 = nullptr;
      
    memset(father, 0, (size + 1) * sizeof(int));

    // Looking for node which has two sources
    for (auto &iter : edges) {
      if (father[iter[1]]) {
        // found
        doubleSourceEdge1 = {
          father[iter[1]], iter[1]
        };

        doubleSourceEdge2 = iter;

        // break;
      }
      father[iter[1]] = iter[0];
    }

    for (int i = 1; i <= size; ++i) father[i] = i;
    // Looking for an edge which forms a circular path
    for (auto &iter: edges) {
      if (doubleSourceEdge2 && iter == *doubleSourceEdge2) continue;

      parent1 = findParent(father, iter[0]);
      parent2 = findParent(father, iter[1]);

      if (parent1 == parent2) {
        // found
        if (doubleSourceEdge1.empty())
          return iter;
        else 
          return doubleSourceEdge1;
      }
      father[iter[1]] = iter[0];
    }
    return doubleSourceEdge2;
  }

  int findParent(int *&father, int index) {
    if (index == father[index])
      return index;
    else 
      return father[index] = findParent(father, father[index]);
  }
};
# Algorithm, Leetcode
Leetcode 839. Similar String Groups
Make Full Use of Your VPS Server
Follow

Links

Categories

Tag Cloud

Algorithm Assignment Blockchain Cloud Service Decision Tree Ensemble Learning Ethereum Github Pages Gitment Golang JavaScript Leetcode Machine Learning OpenAPI RESTful Remote Floder SSAD Service Computing Unity3D VPS server WEB Windows

Recent

Archives

Tags

Algorithm 15
Assignment 5
Blockchain 1
Cloud Service 2
Decision Tree 3
Ensemble Learning 3
Ethereum 1
Github Pages 1
Gitment 1
Golang 2
JavaScript 3
Leetcode 14
Machine Learning 3
OpenAPI 1
RESTful 1
Remote Floder 1
SSAD 7
Service Computing 4
Unity3D 9
VPS server 1
WEB 6
Windows 1

Recent

Archives

Tags

Algorithm 15
Assignment 5
Blockchain 1
Cloud Service 2
Decision Tree 3
Ensemble Learning 3
Ethereum 1
Github Pages 1
Gitment 1
Golang 2
JavaScript 3
Leetcode 14
Machine Learning 3
OpenAPI 1
RESTful 1
Remote Floder 1
SSAD 7
Service Computing 4
Unity3D 9
VPS server 1
WEB 6
Windows 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×