Reachable Nodes With Restrictions

class Solution {
public:
    void explore(int node, int& count, vector<vector<int>>& adjList, vector<bool>& visited) {
        // Increment count for each node visited
        count++;
        visited[node] = true;
        
        // Explore adjacent nodes that are not visited
        for (auto neighbor : adjList[node]) {
            if (!visited[neighbor]) {
                explore(neighbor, count, adjList, visited);
            }
        }
    }
    
    int findReachable(int nodes, vector<vector<int>>& edgesList, vector<int>& blockList) {
        // Initialize adjacency list for nodes
        vector<vector<int>> adjList(nodes);
        for (auto edge : edgesList) {
            int first = edge[0], second = edge[1];
            adjList[first].push_back(second);
            adjList[second].push_back(first);
        }
        
        // Set restricted nodes as visited
        vector<bool> visited(nodes, false);
        for (auto blocked : blockList) {
             visited[blocked] = true;
        }
        
        int result = 0;
        explore(0, result, adjList, visited);
        return result;
    }
};

This C++ solution tackles the problem of determining the number of nodes reachable in an undirected graph, with certain nodes being restricted. The implementation utilizes a depth-first search (DFS) technique, incorporating an adjacency list for graph representation and a boolean vector for tracking visited nodes, including restricted ones.

Solution Process

• Adjacency List Construction:

  • An adjacency list is formed from the given list of edges. For each pair of connected nodes in the edgesList, the connection is established bidirectionally.

• Setting Up Restrictions:

  • A vector named visited initializes with all nodes set to false. Nodes that are in the blockList are then marked as true in visited to denote that these nodes are not to be visited during the DFS traversal.

• DFS Implementation:

  • The DFS starts from node 0.
  • A helper function explore is used to traverse the graph. It marks the current node as visited and explores each adjacent node that has not been visited yet, avoiding the restricted nodes. This function keeps a running count of all nodes that have been visited.

• Count of Reachable Nodes:

  • After the exploration, the count of reachable nodes is returned. The count reflects the number of nodes that can be reached from node 0, excluding the nodes that are restricted.

Key Features and Considerations

• Handling of Connected Components:

  • The solution assumes that the graph is connected or that node 0 has paths to all other non-restricted nodes. For graphs that aren’t fully connected, modifications are necessary to handle other components.

• Efficiency:

  • The DFS approach ensures that each node and edge is visited once in the best-case scenario, barring the restricted nodes, resulting in a time complexity approximately of O(V + E), where V is the number of vertices and E is the number of edges.

• Initialization of Data Structures:

  • Both the adjacency list and the visited vector are crucial for efficient access and traversal. Adjustments to the graph input or blocked nodes input can be managed by simply updating these structures.

This approach primarily uses standard graph traversal techniques and data structures for graph representation, ensuring clarity, efficiency, and adaptability for diverse graph-related problems.

class GraphTraversal {
    private int counter = 0;

    private void search(int node, Map<Integer, List<Integer>> adjList, Set<Integer> visited) {
        counter++;
        visited.add(node);
        
        for (int neighbor : adjList.get(node)) {
            if (!visited.contains(neighbor)) {
                search(neighbor, adjList, visited);
            }
        }    
    }
    
    public int countReachableNodes(int count, int[][] connections, int[] noAccess) {
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        for (int[] connection : connections) {
            int x = connection[0], y = connection[1];
            adjList.computeIfAbsent(x, k -> new ArrayList<>()).add(y);
            adjList.computeIfAbsent(y, k -> new ArrayList<>()).add(x);
        }
        
        Set<Integer> visited = new HashSet<>();
        for (int restrict : noAccess) {
            visited.add(restrict);
        }
        
        search(0, adjList, visited);
        return counter;
    }
}

This Java solution pertains to the problem of counting reachable nodes within a graph, given certain nodes that are not accessible. The solution is implemented with a class GraphTraversal containing key methods to handle the graph traversal and reachability analysis.

The approach involves:

• Building an adjacency list adjList from the input array connections. This list maps each node to its neighbors facilitating undirected graph traversal.
• Handling restricted nodes by adding them to a visited HashSet, which ensures these nodes are not accessible during traversal.
• The primary traversal method search employs Depth First Search (DFS) to explore nodes, counting each accessible node starting from a specific node (node 0 in this case).
• The search method is recursively called for unvisited neighbors found in the adjacency list, thereby recognizing all connected nodes that aren't restricted.
• The countReachableNodes method orchestrates the initialization and execution of the search process and returns the total count of reachable nodes.

The solution uses two primary data structures:

• A HashMap for an adjacency list to manage the mapping of each node to its connected nodes efficiently.
• A HashSet to handle visited and restricted nodes ensuring nodes are visited once and restricted nodes are avoided.

This approach ensures effective traversal through recursive logic and returns an accurate count of the nodes reachable from the starting node, considering any restrictions.

class Solution:
    def totalReachableNodes(self, nodes: int, connections: List[List[int]], banned: List[int]) -> int:
        # Creating a map to track neighbors of each node from edges
        edges_map = collections.defaultdict(list)
        for vertex1, vertex2 in connections:
            edges_map[vertex1].append(vertex2)
            edges_map[vertex2].append(vertex1)
        
        # Using a list to track visited nodes, setting restricted nodes as already visited
        visited = [False] * nodes
        for res_node in banned:
            visited[res_node] = True
        
        def traverse(node):
            # Increment total reachable count and mark current node as visited
            self.reachable_count += 1
            visited[node] = True
            
            # Recursively visit all connected nodes that haven't been visited
            for neighbor in edges_map[node]:
                if not visited[neighbor]:
                    traverse(neighbor)
                    
        self.reachable_count = 0
        traverse(0)  # Start traversal from node 0 (assumed root node)
        return self.reachable_count

The Python solution provided calculates the total number of nodes that can be reached in an undirected graph, given some nodes are banned from being visited. The graph is represented by its connection pairs and a list of banned nodes. The solution employs a depth-first search (DFS) traversal to explore reachable nodes, initiated from node 0 (assuming it's not banned).

• Firstly, the solution constructs an adjacency list (edges_map) from the list of edges (connections) which depicts direct connections between nodes.
• It initializes a list (visited) that keeps track of which nodes have been visited or are banned. Nodes listed in banned are set as visited from the start.
• The main function traverse is defined to perform DFS:
  • It increments a counter (reachable_count) each time a node is visited.
  • It then marks the currently visited node and recursively visits its neighboring nodes if they have not been visited yet.
• The traversal starts at node 0, and after traversing, the total count of reachable nodes is returned.

Here are the steps the function goes through:

1. Initialize the adjacency list for node connections.
2. Mark all banned nodes as visited to prevent visiting them.
3. Define and use a recursive DFS function to count all reachable nodes starting from the desired node, typically node 0.
4. Execute the DFS and calculate the total number of reachable nodes excluding the banned ones.

The function handles the scenario where certain nodes are restricted, effectively counting only those nodes that can be reached through allowed paths.