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
function findConnectedComponents(graph) {
  // Set to keep track of visited vertices
  const visited = new Set();
  
  // Array to store all connected components
  const components = [];
  
  // For each vertex in the graph
  for (const vertex in graph) {
    // If this vertex has not been visited yet
    if (!visited.has(vertex)) {
      // Find all vertices in the same component as this vertex
      const component = bfsComponent(graph, vertex, visited);
      
      // Add this component to the list of components
      components.push(component);
    }
  }
  
  return components;
}
 
function bfsComponent(graph, startVertex, visited) {
  // Queue for BFS
  const queue = [startVertex];
  
  // Mark the start vertex as visited
  visited.add(startVertex);
  
  // Array to store vertices in this component
  const component = [startVertex];
  
  // While there are vertices in the queue
  while (queue.length > 0) {
    // Dequeue a vertex from the queue
    const currentVertex = queue.shift();
    
    // Get all adjacent vertices of the dequeued vertex
    for (const neighbor of graph[currentVertex]) {
      // If this adjacent vertex has not been visited
      if (!visited.has(neighbor)) {
        // Mark it as visited and enqueue it
        visited.add(neighbor);
        queue.push(neighbor);
        
        // Add it to this component
        component.push(neighbor);
      }
    }
  }
  
  return component;
}
 
// Example usage:
const graph = {
  'A': ['B'],
  'B': ['A', 'C'],
  'C': ['B'],
  'D': ['E'],
  'E': ['D', 'F'],
  'F': ['E'],
  'G': []
};
 
const components = findConnectedComponents(graph);
console.log(components);
// Output: [['A', 'B', 'C'], ['D', 'E', 'F'], ['G']]

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
function numIslands(grid) {
  if (!grid || grid.length === 0) {
    return 0;
  }
  
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;
  
  // Directions: up, right, down, left
  const directions = [[-1, 0], [0, 1], [1, 0], [0, -1]];
  
  // Function to check if a cell is valid and is land
  function isValid(row, col) {
    return row >= 0 && row < rows && col >= 0 && col < cols && grid[row][col] === '1';
  }
  
  // BFS to mark all connected land cells as visited
  function bfs(row, col) {
    const queue = [[row, col]];
    grid[row][col] = '0'; // Mark as visited by changing '1' to '0'
    
    while (queue.length > 0) {
      const [currentRow, currentCol] = queue.shift();
      
      // Check all four directions
      for (const [dr, dc] of directions) {
        const newRow = currentRow + dr;
        const newCol = currentCol + dc;
        
        if (isValid(newRow, newCol)) {
          queue.push([newRow, newCol]);
          grid[newRow][newCol] = '0'; // Mark as visited
        }
      }
    }
  }
  
  // Iterate through each cell in the grid
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      // If we find a land cell, start BFS and increment count
      if (grid[i][j] === '1') {
        count++;
        bfs(i, j);
      }
    }
  }
  
  return count;
}
 
// Example usage:
const grid = [
  ['1', '1', '0', '0', '0'],
  ['1', '1', '0', '0', '0'],
  ['0', '0', '1', '0', '0'],
  ['0', '0', '0', '1', '1']
];
 
const islands = numIslands(grid);
console.log(islands); // Output: 3