Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

It is not because we see hope, but because we see hope. ‘

Day 54 2021.03.03

323. The number of connected components in an undirected graph

  • Leetcode: leetcode-cn.com/problems/nu…
  • Difficulty: Medium
  • Method: BFS breadth-first search

Topic describes

  • You have a containnA graph of nodes. Given an integernAnd an arrayedges, includingedges[i] = [ai, bi]Said in the figureai 和 bi There’s an edge between them.
  • Returns the number of connected components in the graph.

The sample

  • Example 1

Edges input: n = 5, edges = [[0, 1], [1, 2], [3, 4]] Output: 2Copy the code
  • Example 2

Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4]] output: 1Copy the code

prompt

  • 1 <= n <= 2000
  • 1 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= ai <= bi < n
  • ai ! = bi
  • There are no duplicate edges in the edges

Expand knowledge (breadth-first traversal)

  • Example in life: When I was in college, one of my notes was incomplete. If you want to fix the notes, then you need toAsk your class if anyone has taken notes (level 1); If you still can’t find the notes, you need toAsk the teacher if the students in other classes take notes. (Level 2). This layer by layer problem solving, isbfs.
  • Implemented data structure: queue
  • Application: Find shortest path in unauthorized graph
    • In the unempowered graph, because of the breadth-first traversal itself, assuming that the source point is source, only after traversing all the nodes whose distance from source point source is D, can we traverse all the nodes whose distance from source point source is D + 1.
    • You can also use the experience of “shortest line segment between two points” to help understand the following conclusion: The path from source to target must be the shortest if you walk in a straight line.
  • Note: no right to traverse in the graph, join the queue must be immediately marked as accessed

Thought analysis

  • sincebfsIs traversal layer by layer, so for each node in the undirected graph can also be traversal layer by layer.
  • Overall idea :(parameters to be prepared)
    • usevisitedThe array records the edges that have been traversed, using a two-dimensional arrayvisited[x][y] = 0 || 1
    • There may be a separate node with no edge connected to it. It is also a connected component, so it needs to be usedpointArray, which records the nodes that have been traversed. The final result needs to add the number of nodes that have not been traversed.
  • Loop through the array of edges, putting in edges that are not marked (that is, not walked)bfsIn a function.
  • bfsFunction: The edges that start or end with the current node in the unauthorized graph belong to the first layer, and the edges of the first layer are pressed into the queue in turnqueueAfter writing down the length of the first layer, startforIterate over the next connected edge of each edge in the first layer.
    • When looking for the next connected edge, note that the node that may be connected to the previous edge is inyRather thanxBecause it’s an unauthorized graph, it has no direction. Sample:[[2, 3], [1, 2], [1, 3]]
    • So here: when judging, the current fixed node and the next edgexandyCompare them separately, and if they are the same, they can be connected. Then modify the current order of edge connection (mainly to considervisitedArray recording problem before modifying the original string).
  • Each time, the edges that can be found connected are put into the queue, layer by layer, and finally all the connected nodes in the undirected graph will be found.
  • Review: multiple processesbfsThe entry node is somewhat similar to multi-sourcebfs.

ACcode

var countComponents = function(n, edges) {
  // Undirected graph traverses from a node
  // Iterate over the edges of the array
  let ans = 0;
  let len = edges.length;
  let cha = n;
  // if(n == 2) return 1;
  // Other cases
  let point = new Array(n).fill(0);
  // Encapsulate the loop
  let queue = new Array(a);function cycle (x) {
    for(let i = 0; i < len; i++) {
      // Undirected graphs need to iterate over some cases
      // Current thinking solution: as long as there is this node to find out
      // If it is in the back, modify the original array. Visited still uses the original mark
      if(edges[i][0] == x && visited[edges[i][0]][edges[i][1= =]]0){
        queue.push(edges[i]);
        visited[edges[i][0]][edges[i][1]] = 1;
      }
      if(edges[i][1] == x && visited[edges[i][0]][edges[i][1= =]]0) {
        // The following value is the current starting point, need to change the value, and then save
        let tempt = edges[i][0];
        edges[i][0] = edges[i][1];
        edges[i][1] = tempt;
        queue.push(edges[i]);
        visited[edges[i][0]][edges[i][1]] = 1; }}}function bfs(cur) {
    // Currently as the first layer
    queue.push(cur);
    visited[cur[0]][cur[1]] = 1;
    let x = cur[0];
    // See if there are any other nodes with the same beginning in the array
    cycle(x);
    // console.log(' find the original ',queue);
    // Find all the same nodes
    while(queue.length ! =0) {
      let curLen = queue.length;
      for(let j = 0; j < curLen; j++) {
        let front = queue.shift();
        // console.log(front);
        visited[front[0]][front[1]] = 1;
        point[front[1]] = 1;
        cycle(front[1]); }}}// Marks an array to record whether the current edge has run
  let visited = new Array(n);
  for(let i = 0; i < n; i++) {
    visited[i] = new Array(n).fill(0);
  }
  for(let i = 0; i < len; i++) {
    let x = edges[i][0];
    let y = edges[i][1];
    if(visited[x][y] == 0){
      ans++;
      point[x] = 1; bfs(edges[i]); }}for(let i = 0; i < n; i++) {
    if(point[i] == 0) ans++;
  }
  // The rest of the initial nodes are 0
  return ans;
};
Copy the code

conclusion

  • Characteristics of undirected graphs:(2, 1] and [1, 2]It’s the same thing, because there’s no direction.