This is the 16th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Note: Part of the content and pictures from the network, if there is any infringement, please contact me (home page has the public number: Small siege city Lion science front end)

Author: small front siege city lion, home: small front siege city lion’s home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front end siege lion

The copyright belongs to the author. Commercial reprint please contact the author to obtain authorization, non-commercial reprint please indicate the source.

LeetCode 684. Redundant connections – JavaScript

Topic describes

In this problem, a tree is an undirected graph that is connected and without a loop.

Enter a graph consisting of a graph with N nodes (node values do not repeat 1, 2… , N) and an additional edge. The two vertices of the additional edge are contained between 1 and N, and this additional edge does not belong to an existing edge in the tree.

The resulting graph is a two-dimensional array of edges. The elements of each edge are a pair of [u, v] such that u < v represents the edge of an undirected graph that joins vertices u and v.

Returns an edge that can be deleted so that the resulting graph is a tree with N nodes. If there are more than one answer, the last edge in the two-dimensional array is returned. Answer edges [u, v] should satisfy the same format u < v.

Subject analysis

It’s a very long problem, basically it’s a tree, and then the input gives you all the connections to the nodes in that tree, plus one more. This extra edge is not going to fit the definition of a tree. For example, in the following example, the extra edge [1, 4] forms a ring:

Input: [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]] output: [1, 4] explain: given the undirected the graph is: 5-1-2 | | 4 to 3Copy the code

Solution approach

Solution 1: Parallel set lookup (DSU)

For a tree, there is a single root node. The u and V in all edges [u, v] should all belong to the same set, as they are all the root nodes of the join point in terms of shape.

If [p, q] is a repeating edge, then p and q should have previously been recorded in the same set. So every time you add a new edge, just check to see if the set already contains nodes on both sides of the edge.

This relationship can be described using a merge set, and a merge set can quickly find a set of nodes and quickly merge two sets. Code implementation is as follows:

class UnionFind {
  constructor() {
    this.parent = new Map(a); }// Find the collection where the element resides
  find(x) {
    while (this.parent.has(x)) {
      x = this.parent.get(x);
    }
    return x;
  }
​
  // Merge the two sets
  union(p, q) {
    const rootP = this.find(p);
    const rootQ = this.find(q);
    if(rootP ! == rootQ) {this.parent.set(this.find(p), this.find(q)); }}}var findRedundantConnection = function(edges) {
  const uf = new UnionFind();
​
  for (const edge of edges) {
    const p = edge[0];
    const q = edge[1];
    if (uf.find(p) === uf.find(q)) {
      return [p, q];
    }
    uf.union(p, q);
  }
  return [-1, -1];
};
Copy the code
Method 2: DFS

Use DFS for the edge [u, v] to check whether u and v are connected. If so, it is a repeating edge.

var findRedundantConnection = function(edges) {
    const grah = [], visited = new Uint8Array(edges.length + 1), d = (x, y) = > {
        if (x === y) return true
        if(visited[x] || ! grah[x])return false
        visited[x] = 1
        for (let i = 0; i < grah[x].length; i++) if (d(grah[x][i], y)) return true
    }
    for (let i = 0; i < edges.length; i++) {
        const x = edges[i][0], y = edges[i][1]
        visited.fill(0)
        if (d(x, y)) return [x, y]
        if(! grah[x]) grah[x] = [] grah[x].push(y)if(! grah[y]) grah[y] = [] grah[y].push(x) } };Copy the code

Think outside the box: Why can’t you use sets?

After completing the solution of looking up the Set, I used the data structure Set to try this problem, as shown below:

var findRedundantConnection = function(edges) {
  const set = new Set(a);for (const edge of edges) {
    if (set.has(edge[0]) && set.has(edge[1]) {return edge;
    }
    set.add(edge[0]).add(edge[1]);
  }
  return [-1, -1];
};
Copy the code

The result, of course, is that there is no AC. The error use case is:

Input: [[3,4],[1,2],[2,4],[3,5],[2,5]Copy the code

Analysis: There is no guarantee that all nodes in a Set belong to the same “connected component”. For example, 3 and 4 are connected, 1 and 2 are connected, but these are two connected components.

By saving the parent point of the node, the query set keeps searching, and the final node found can be regarded as the root node of the connected component. All the other nodes in the connected component point to it, so it can be used to identify the connected component.

Thank you for reading, I hope it can help you, if there are mistakes or infringement of the article, you can leave a message in the comment area or add the public account in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for supporting ❤