Horje
Ascending insertion of elements in graph

Given a graph consisting of vertices numbered from 1 to N and having M bidirectional edges connecting vertices u and v. Let P denote an entrance vertex. N elements are numbered from 1 to N and inserted into the graph from the entrance P (1<=P<=N) in ascending order. A filled vertex is a vertex where an element is already placed. An element e (1<=e<=N) is said to be placed if it can reach the eth vertex starting from vertex P without crossing any other filled vertex; otherwise, the element cannot be placed and is skipped; hence the eth vertex remains unfilled. Calculate the number of filled vertex/placed elements in the graph.

Examples:

Input: N = 4, M = 4, P = 4, Edges = {{ 1, 3 }, { 1, 4 }, { 2, 3 }, { 2, 4 }}
Output: 3
Explanation: Lets insert the elements in ascending order from 1 to N

  • E = 1. The element is inserted from 4->1. So count = 1
  • E = 2. The element is inserted from 4->2. So count = 2
  • E = 3. The two paths from P i.e. 4 to 3 are 4->1->3 and 4->2->3. In first path the element cannot be traversed through 1 as it is already filled. Similarly for the second path the element cannot travel as the vertex 2 is already filled. So skip element 3.
  • E = 4. The element number if the starting vertex and is empty so vertex 4 is filled. Count = 3

Input: N = 5, M = 4, P = 3, Edges = {{1, 2 }, { 2, 3 }, { 3, 4 }, { 4, 5}}
Output: 3
Explanation: Lets insert the elements in ascending order from 1 to N

  • E = 1. Traverse from 3->2->1 and place the element. Vertex 1 is now filled. Count = 1
  • E = 2. Traverse from 3->2 and place the element. Vertex 2 is now filled. Count = 2
  • E = 3. It is the starting vertex where the element is to be placed. So vertex 3 is filled. Count = 3
  • E = 4. Starting vertex is 3 ie. P and now vertex 3 is already filled. Hence from P no more vertices can be visited to be filled by the elements.
  • E = 5. Similar case as of E = 4 it cannot be visited. Hence the final count is Count = 3

Approach: To solve the problem using BFS/DFS follow the below idea:

Problem translates to remove the vertex i if it can be reached from vertex P otherwise skip the element. Inshort for each vertex from 1 to N we have to check is there exist a path to vertex i from vertex P. If there exist a path remove that vertex and then check for the next vertex in ascending order on the modified graph. This check can be done using BFS or DFS for each vertex.

Follow the steps to code:

  • The solve function builds the adjacency list representation of the graph and calls the BFS function to determine the number of filled vertices.
  • Once the adjacency list is built BFS call is made.
  • In the BFS,
    • Vector visited, and isRemoved is initialized to false. Visited keeps track of the visited vertices and isRemoved keeps track of the filled vertices that can be removed from the graph.
    • Each element e is then iterated in ascending order
    • Each neighboring vertices of vertex U from the queue are then iterated such that the vertices are not visited yet and are also present inside the graph, i.e. isRemoved is set to false for a particular vertex.
    • If the vertex e is reachable from vertex P, then isRemoved for the vertex e is marked True.
    • Finally, count the vertices for which isRemoved is true and return the count.
  • Output the final count

Below is the implementation of the above idea:

C++

// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
 
// Perform BFS traversal from the starting vertex
// P and mark reachable vertices for removal
int BFS(int N, int P, vector<vector<int> >& adj)
{
    queue<int> Q;
    vector<bool> vis, isRemoved(N + 1, 0);
 
    // Iterate over each vertex to determine
    // reachability from the starting vertex
    for (int e = 1; e <= N; e++) {
 
        // Initialize the queue, visited array,
        // and mark the starting vertex as visited
        Q = queue<int>();
        Q.push(P);
        vis.assign(N + 1, 0);
        vis[P] = 1;
 
        // Skip if the starting vertex P is
        // already marked for removal
        if (isRemoved[P]) {
            continue;
        }
 
        // BFS traversal
        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
 
            // Visit all neighbors of the current
            // vertex u
            for (auto v : adj[u]) {
 
                // If the neighbor v is not visited
                // markedand not for removal, mark
                // it as visited and enqueue it
                if (vis[v] == 0 and isRemoved[v] == 0) {
                    vis[v] = 1;
                    Q.push(v);
                }
            }
        }
 
        // If the current vertex e is reachable
        // from the starting vertex, mark it
        // for removal
        if (vis[e]) {
            isRemoved[e] = 1;
        }
    }
 
    // Count the number of vertices
    // marked for removal
    int count = 0;
    for (int i = 1; i <= N; i++) {
        if (isRemoved[i]) {
            count++;
        }
    }
    return count;
}
 
void solve(int N, int M, int P, vector<vector<int> >& edges)
{
    vector<vector<int> > adj(N + 1);
 
    // Build the adjacency list representation
    // of the graph
    for (auto edge : edges) {
        int u = edge[0], v = edge[1];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    // Call BFS to determine the number of
    // filled vertices
    int filledVertices = BFS(N, P, adj);
 
    cout << "Number of filled vertices are: "
         << filledVertices << "\n";
}
 
// Drivers code
int main()
{
    int N, M, P;
 
    // Sample input
    N = 4, M = 4, P = 4;
    vector<vector<int> > edges
        = { { 1, 3 }, { 1, 4 }, { 2, 3 }, { 2, 4 } };
 
    // Function call
    solve(N, M, P, edges);
 
    return 0;
}

Java

// Java code for the above approach:
 
import java.util.*;
 
public class GFG {
 
    // Perform BFS traversal from the starting vertex P and mark reachable vertices for removal
    static int BFS(int N, int P, List<List<Integer>> adj) {
        Queue<Integer> Q = new LinkedList<>();
        List<Boolean> vis = new ArrayList<>();
        List<Boolean> isRemoved = new ArrayList<>(Collections.nCopies(N + 1, false));
 
        // Iterate over each vertex to determine reachability from the starting vertex P
        for (int e = 1; e <= N; e++) {
            // Initialize the queue, visited array, and mark the starting vertex as visited
            Q.clear();
            Q.add(P);
            vis.clear();
            vis.addAll(Collections.nCopies(N + 1, false));
            vis.set(P, true);
 
            // Skip if the starting vertex P is already marked for removal
            if (isRemoved.get(P)) {
                continue;
            }
 
            // BFS traversal
            while (!Q.isEmpty()) {
                int u = Q.poll();
 
                // Visit all neighbors of the current vertex u
                for (int v : adj.get(u)) {
                    // If the neighbor v is not visited, marked, and not for removal,
                    // mark it as visited and enqueue it
                    if (!vis.get(v) && !isRemoved.get(v)) {
                        vis.set(v, true);
                        Q.add(v);
                    }
                }
            }
 
            // If the current vertex e is reachable from the starting vertex, mark it for removal
            if (vis.get(e)) {
                isRemoved.set(e, true);
            }
        }
 
        // Count the number of vertices marked for removal
        int count = 0;
        for (int i = 1; i <= N; i++) {
            if (isRemoved.get(i)) {
                count++;
            }
        }
        return count;
    }
 
    static void solve(int N, int M, int P, List<List<Integer>> edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            adj.add(new ArrayList<>());
        }
        for (List<Integer> edge : edges) {
            int u = edge.get(0);
            int v = edge.get(1);
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
 
        // Call BFS to determine the number of filled vertices
        int filledVertices = BFS(N, P, adj);
 
        // Output the result
        System.out.println("Number of filled vertices are: " + filledVertices);
    }
 
    public static void main(String[] args) {
        int N, M, P;
 
        // Sample input
        N = 4;
        M = 4;
        P = 4;
        List<List<Integer>> edges = new ArrayList<>();
        edges.add(Arrays.asList(1, 3));
        edges.add(Arrays.asList(1, 4));
        edges.add(Arrays.asList(2, 3));
        edges.add(Arrays.asList(2, 4));
 
        // Function call
        solve(N, M, P, edges);
    }
}
// This code is contributed by uttamdp_10

Python3

from collections import deque
 
 
def bfs(N, P, adj):
    queue = deque()  # Create a queue for BFS traversal
    is_removed = [False] * (N + 1)
 
    count = 0  # Initialize count of filled vertices
 
    for e in range(1, N + 1):
        queue.clear()  # Clear the queue
        queue.append(P)  # Start BFS from the starting vertex P
        visited = [False] * (N + 1)  # Initialize visited array
    # Initialize array to track removed vertices
        visited[P] = True  # Mark P as visited
 
        if is_removed[P]:  # If P is already marked for removal, skip
            continue
 
        while queue:
            u = queue.popleft()  # Get the vertex from the front of the queue
 
            for v in adj[u]:
                if not visited[v] and not is_removed[v]:
                    visited[v] = True  # Mark the neighbor v as visited
                    # Enqueue the neighbor v for further traversal
                    queue.append(v)
        if visited[e]:
            is_removed[e] = True  # Mark the vertex e for removal
 
    for e in range(1, N + 1):
        if is_removed[e]:
            count += 1
 
    return count
 
 
def solve(N, M, P, edges):
    adj = [[] for _ in range(N + 1)]  # Create an empty adjacency list
 
    # Build the adjacency list representation of the graph
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
 
    # Perform BFS traversal to find filled vertices
    filled_vertices = bfs(N, P, adj)
 
    print("Number of filled vertices are:", filled_vertices)
 
 
if __name__ == "__main__":
    N, M, P = 4, 4, 4  # Sample input values
    edges = [[1, 3], [1, 4], [2, 3], [2, 4]]  # Sample edges
 
    # Call the solve function to find the number of filled vertices
    solve(N, M, P, edges)

C#

// C# code for the above approach:
 
using System;
using System.Collections.Generic;
using System.Linq;
 
public class GFG
{
    // Perform BFS traversal from the starting vertex P and mark reachable vertices for removal
    static int BFS(int N, int P, List<List<int>> adj)
    {
        Queue<int> Q = new Queue<int>();
        List<bool> vis = new List<bool>(new bool[N + 1]);
        List<bool> isRemoved = Enumerable.Repeat(false, N + 1).ToList();
 
        // Iterate over each vertex to determine reachability from the starting vertex P
        for (int e = 1; e <= N; e++)
        {
            // Initialize the queue, visited array, and mark the starting vertex as visited
            Q.Clear();
            Q.Enqueue(P);
            vis.Clear();
            vis.AddRange(Enumerable.Repeat(false, N + 1));
            vis[P] = true;
 
            // Skip if the starting vertex P is already marked for removal
            if (isRemoved[P])
            {
                continue;
            }
 
            // BFS traversal
            while (Q.Count > 0)
            {
                int u = Q.Dequeue();
 
                // Visit all neighbors of the current vertex u
                foreach (int v in adj[u])
                {
                    // If the neighbor v is not visited, marked, and not for removal,
                    // mark it as visited and enqueue it
                    if (!vis[v] && !isRemoved[v])
                    {
                        vis[v] = true;
                        Q.Enqueue(v);
                    }
                }
            }
 
            // If the current vertex e is reachable from the starting vertex, mark it for removal
            if (vis[e])
            {
                isRemoved[e] = true;
            }
        }
 
        // Count the number of vertices marked for removal
        int count = 0;
        for (int i = 1; i <= N; i++)
        {
            if (isRemoved[i])
            {
                count++;
            }
        }
        return count;
    }
 
    static void solve(int N, int M, int P, List<List<int>> edges)
    {
        List<List<int>> adj = new List<List<int>>();
        for (int i = 0; i <= N; i++)
        {
            adj.Add(new List<int>());
        }
        foreach (List<int> edge in edges)
        {
            int u = edge[0];
            int v = edge[1];
            adj[u].Add(v);
            adj[v].Add(u);
        }
 
        // Call BFS to determine the number of filled vertices
        int filledVertices = BFS(N, P, adj);
 
        // Output the result
        Console.WriteLine("Number of filled vertices are: " + filledVertices);
    }
 
    public static void Main(string[] args)
    {
        int N, M, P;
 
        // Sample input
        N = 4;
        M = 4;
        P = 4;
        List<List<int>> edges = new List<List<int>>
        {
            new List<int> { 1, 3 },
            new List<int> { 1, 4 },
            new List<int> { 2, 3 },
            new List<int> { 2, 4 }
        };
 
        // Function call
        solve(N, M, P, edges);
    }
}
 
// This code is contributed by uttamdp_10

Javascript

function BFS(N, P, adj) {
    const Q = [];
    const vis = Array(N + 1).fill(false);
    const isRemoved = Array(N + 1).fill(false);
 
    for (let e = 1; e <= N; e++) {
        Q.length = 0;
        Q.push(P);
        vis.fill(false);
        vis[P] = true;
 
        if (isRemoved[P]) {
            continue;
        }
 
        while (Q.length > 0) {
            const u = Q.shift();
 
            for (const v of adj[u]) {
                if (!vis[v] && !isRemoved[v]) {
                    vis[v] = true;
                    Q.push(v);
                }
            }
        }
 
        if (vis[e]) {
            isRemoved[e] = true;
        }
    }
 
    let count = 0;
    for (let i = 1; i <= N; i++) {
        if (isRemoved[i]) {
            count++;
        }
    }
    return count;
}
 
function solve(N, M, P, edges) {
    const adj = Array.from({ length: N + 1 }, () => []);
 
    for (const edge of edges) {
        const u = edge[0];
        const v = edge[1];
        adj[u].push(v);
        adj[v].push(u);
    }
 
    const filledVertices = BFS(N, P, adj);
    console.log("Number of filled vertices are:", filledVertices);
}
 
// Sample input
const N = 4;
const M = 4;
const P = 4;
const edges = [
    [1, 3],
    [1, 4],
    [2, 3],
    [2, 4]
];
 
// Function call
solve(N, M, P, edges);
 
// This code is contributed by Dwaipayan Bandyopadhyay

Output

Number of filled vertices are: 3

Time Complexity: O(N*(N+M))
Auxiliary Space: O(N)

Efficient Approach: Using Dijkstra Algorithm

  • The key idea here to note is that we can fill the vertex v if it can be traversed from vertices greater than or equal to v. Also we are using a single source vertex to check if we can traverse each vertex in ascending order. Then vertex v can only be filled if it is traversed from S by vertices greater than or equal to V which means for each vertex v we can store the maximum minimum vertex that can be traversed. If this value is greater than or equal to v then the vertex can be filled. Else it cannot be filled as to travel to that vertex from S we have to traverse a vertex which is smaller than v. And the vertex smaller than v is already processed as the vertices have to be filled in ascending order.
  • To ensure that we traverse through the larger values and then to smaller ones, we can use the concept from Dijkstra to use a priority queue instead of a regular one. By doing this, we process the vertices in the order of decreasing the maximum, minimum value to ensure that we only consider the paths that maximize the minimum index encountered. Overall, the priority queue helps select the vertices in the order that maximizes the minimum index encountered along the paths.

Follow the steps to code:

  • The solve function builds the adjacency list representation of the graph and calls the BFS function to determine the number of filled vertices.
  • Once the adjacency list is built, a Dijkstra call is made.
  • In the Dijkstra,
    • Initialize two vectors vis and dist. Vis keeps track of whether the vertex is previously visited, and dist array stores the maximum minimum vertex value for vertex i. dist[i] denotes the maximum of the minimum vertices that must be traversed to reach vertex i.
    • Declare a priority queue of type max heap to extract the vertices in decreasing order of minimum vertex so that to get the maximum and minimum value and iterate the graph in the order of decreasing the maximum and minimum value to ensure that we only consider the paths that maximize the minimum index encountered.
    • While visiting the neighbors
      • Update the maximum minimum value for the neighbors
      • If the neighbor’s current maximum minimum value is smaller than the calculated value, update it
    • Now if the dist[i] >= i, then the vertex i is reachable from vertex S. This is because if the dist[i] was less than i, then vertex dist[i] will be filled first as we are inserting the elements in the ascending order. And hence as the only path to vertex i was from dist[i] we could not reach vertex i and had to skip it.
    • Store the count of such vertices.
  • Output the count.the

Below is the implementation of the above idea:

C++

// C++ code of above approach
#include <bits/stdc++.h>
using namespace std;
 
int Dijkstra(int N, int P, vector<vector<int> >& adj)
{
 
    // Initialize distance array and visited array
    vector<int> dist(N + 1, 0);
    vector<bool> vis(N + 1, 0);
 
    // Priority queue to store vertices and
    // their distances
    priority_queue<pair<int, int> > pq;
    pq.push({ P, P });
    dist[P] = P;
 
    while (!pq.empty()) {
 
        // Get the vertex with the maximum
        // minimum value
        int dis = pq.top().first;
        int u = pq.top().second;
 
        pq.pop();
 
        // If the vertex is already visited,
        // continue to the next iteration
        if (vis[u]) {
            continue;
        }
 
        // Mark the vertex as visited
        vis[u] = 1;
 
        // Update the maximum minimum value for the
        // neighbours
        for (auto v : adj[u]) {
            // Calculate the maximum minimum value
            // for the neighbour
            int d = min(dis, v);
            if (dist[v] < d) {
 
                // If the neighbor's current maximum
                // minimum value is smaller than the
                // calculated value, update it
                dist[v] = d;
                pq.push({ d, v });
            }
        }
    }
 
    // Count the number of vertices with
    // maximum minimum values
    int count = 0;
    for (int i = 1; i <= N; i++) {
        if (i <= dist[i]) {
            count++;
        }
    }
 
    return count;
}
 
void solve(int N, int M, int P, vector<vector<int> >& edges)
{
 
    // Create adjacency list representation
    // of the graph
    vector<vector<int> > adj(N + 1);
    for (auto edge : edges) {
        int u = edge[0], v = edge[1];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    // Call Dijkstra's algorithm to find the
    // maximum minimum values
    int filledVertices = Dijkstra(N, P, adj);
 
    // Output the result
    cout << "Number of filled vertices are: "
         << filledVertices << "\n";
}
 
// Drivers code
int main()
{
 
    int N, M, P;
 
    // Example input
    N = 4, M = 4, P = 4;
    vector<vector<int> > edges
        = { { 1, 3 }, { 1, 4 }, { 2, 3 }, { 2, 4 } };
 
    // Solve the problem
    solve(N, M, P, edges);
 
    return 0;
}

Java

// Java code of above approach:
import java.util.*;
 
public class Main {
 
    static int Dijkstra(int N, int P, List<List<Integer>> adj) {
        // Initialize distance array and visited array
        int[] dist = new int[N + 1];
        Arrays.fill(dist, 0);
        boolean[] vis = new boolean[N + 1];
 
        // Priority queue to store vertices and their distances
        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> b.getKey() - a.getKey());
        pq.offer(new Pair<>(P, P));
        dist[P] = P;
 
        while (!pq.isEmpty()) {
            // Get the vertex with the maximum minimum value
            Pair<Integer, Integer> top = pq.poll();
            int dis = top.getKey();
            int u = top.getValue();
 
            // If the vertex is already visited, continue to the next iteration
            if (vis[u]) {
                continue;
            }
 
            // Mark the vertex as visited
            vis[u] = true;
 
            // Update the maximum minimum value for the neighbours
            for (int v : adj.get(u)) {
                // Calculate the maximum minimum value for the neighbour
                int d = Math.min(dis, v);
                if (dist[v] < d) {
                    // If the neighbor's current maximum minimum value is smaller than the calculated value, update it
                    dist[v] = d;
                    pq.offer(new Pair<>(d, v));
                }
            }
        }
 
        // Count the number of vertices with maximum minimum values
        int count = 0;
        for (int i = 1; i <= N; i++) {
            if (i <= dist[i]) {
                count++;
            }
        }
 
        return count;
    }
 
    static void solve(int N, int M, int P, List<List<Integer>> edges) {
        // Create adjacency list representation of the graph
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            adj.add(new ArrayList<>());
        }
        for (List<Integer> edge : edges) {
            int u = edge.get(0);
            int v = edge.get(1);
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
 
        // Call Dijkstra's algorithm to find the maximum minimum values
        int filledVertices = Dijkstra(N, P, adj);
 
        // Output the result
        System.out.println("Number of filled vertices are: " + filledVertices);
    }
 
    public static void main(String[] args) {
        int N, M, P;
 
        // Example input
        N = 4;
        M = 4;
        P = 4;
        List<List<Integer>> edges = new ArrayList<>();
        edges.add(Arrays.asList(1, 3));
        edges.add(Arrays.asList(1, 4));
        edges.add(Arrays.asList(2, 3));
        edges.add(Arrays.asList(2, 4));
 
        // Solve the problem
        solve(N, M, P, edges);
    }
 
    static class Pair<K, V> {
        private K key;
        private V value;
 
        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }
 
        public K getKey() {
            return key;
        }
 
        public V getValue() {
            return value;
        }
    }
}
 
// This code is contributed by uttamdp_10

Python3

import heapq
 
 
def dijkstra(N, P, adj):
    # Initialize distance array and visited array
    dist = [0] * (N + 1)
    vis = [False] * (N + 1)
    pq = [(P, P)]  # Priority queue to store vertices and their distances
    dist[P] = P
 
    while pq:
        # Get the vertex with the maximum minimum value
        dis, u = heapq.heappop(pq)
 
        if vis[u]:
            continue  # If the vertex is already visited, continue to the next iteration
 
        vis[u] = True  # Mark the vertex as visited
 
        # Update the maximum minimum value for the neighbors
        for v in adj[u]:
            # Calculate the maximum minimum value for the neighbor
            d = min(dis, v)
            if dist[v] < d:
                # If the neighbor's current maximum minimum value is smaller than the calculated value, update it
                dist[v] = d
                heapq.heappush(pq, (d, v))
 
    # Count the number of vertices with maximum minimum values
    count = 0
    for i in range(1, N + 1):
        if i <= dist[i]:
            count += 1
 
    return count
 
 
def solve(N, M, P, edges):
    # Create adjacency list representation of the graph
    adj = [[] for _ in range(N + 1)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
 
    # Call Dijkstra's algorithm to find the maximum minimum values
    filledVertices = dijkstra(N, P, adj)
 
    # Output the result
    print("Number of filled vertices are:", filledVertices)
 
 
if __name__ == "__main__":
 
    # Example input
    N, M, P = 4, 4, 4
    edges = [[1, 3], [1, 4], [2, 3], [2, 4]]
 
    solve(N, M, P, edges)

C#

// C# code of above approach:
using System;
using System.Collections.Generic;
 
public class MainClass
{
    // Perform Dijkstra's algorithm to find the maximum minimum values
    static int Dijkstra(int N, int P, List<List<int>> adj)
    {
        // Initialize distance array and visited array
        int[] dist = new int[N + 1];
        bool[] vis = new bool[N + 1];
        PriorityQueue<(int, int)> pq = new PriorityQueue<(int, int)>(new MaxMinComparer());
        dist[P] = P;
        pq.Enqueue((P, P));
 
        while (pq.Count > 0)
        {
            // Get the vertex with the maximum minimum value
            (int dis, int u) = pq.Dequeue();
 
            if (vis[u])
                continue; // If the vertex is already visited, continue to the next iteration
 
            vis[u] = true; // Mark the vertex as visited
 
            // Update the maximum minimum value for the neighbors
            foreach (int v in adj[u])
            {
                // Calculate the maximum minimum value for the neighbor
                int d = Math.Min(dis, v);
                if (dist[v] < d)
                {
                    // If the neighbor's current maximum minimum value is smaller than the calculated value, update it
                    dist[v] = d;
                    pq.Enqueue((d, v));
                }
            }
        }
 
        // Count the number of vertices with maximum minimum values
        int count = 0;
        for (int i = 1; i <= N; i++)
        {
            if (i <= dist[i])
                count++;
        }
 
        return count;
    }
 
    static void Solve(int N, int M, int P, List<List<int>> edges)
    {
        // Create adjacency list representation of the graph
        List<List<int>> adj = new List<List<int>>();
        for (int i = 0; i <= N; i++)
        {
            adj.Add(new List<int>());
        }
        foreach (List<int> edge in edges)
        {
            int u = edge[0];
            int v = edge[1];
            adj[u].Add(v);
            adj[v].Add(u);
        }
 
        // Call Dijkstra's algorithm to find the maximum minimum values
        int filledVertices = Dijkstra(N, P, adj);
 
        // Output the result
        Console.WriteLine("Number of filled vertices are: " + filledVertices);
    }
 
    public static void Main(string[] args)
    {
        // Example input
        int N = 4, M = 4, P = 4;
        List<List<int>> edges = new List<List<int>>
        {
            new List<int> { 1, 3 },
            new List<int> { 1, 4 },
            new List<int> { 2, 3 },
            new List<int> { 2, 4 }
        };
 
        // Function call
        Solve(N, M, P, edges);
    }
}
 
public class MaxMinComparer : IComparer<(int, int)>
{
    public int Compare((int, int) x, (int, int) y)
    {
        return y.Item1.CompareTo(x.Item1); // Compare in reverse order to get the maximum minimum value at the top of the priority queue
    }
}
 
public class PriorityQueue<T>
{
    private readonly List<T> heap;
    private readonly IComparer<T> comparer;
 
    public PriorityQueue() : this(Comparer<T>.Default)
    {
    }
 
    public PriorityQueue(IComparer<T> comparer)
    {
        this.heap = new List<T>();
        this.comparer = comparer;
    }
 
    public int Count => heap.Count;
 
    public void Enqueue(T item)
    {
        heap.Add(item);
        int i = heap.Count - 1;
        while (i > 0)
        {
            int parent = (i - 1) / 2;
            if (comparer.Compare(heap[parent], item) >= 0)
                break;
            heap[i] = heap[parent];
            i = parent;
        }
        heap[i] = item;
    }
 
    public T Dequeue()
    {
        int n = heap.Count - 1;
        T result = heap[0];
        T item = heap[n];
        heap.RemoveAt(n);
 
        if (n == 0)
            return result;
 
        int i = 0;
        while (true)
        {
            int left = i * 2 + 1;
            if (left >= n)
                break;
            int right = left + 1;
            int child = (right >= n || comparer.Compare(heap[left], heap[right]) >= 0) ? left : right;
            if (comparer.Compare(item, heap[child]) >= 0)
                break;
            heap[i] = heap[child];
            i = child;
        }
        heap[i] = item;
        return result;
    }
 
    public T Peek()
    {
        return heap[0];
    }
}
 
// this code is contributed by uttamdp_10

Javascript

// Javascript implementation
 
function Dijkstra(N, P, adj) {
  // Initialize distance array and visited array
  let dist = new Array(N + 1).fill(0);
  let vis = new Array(N + 1).fill(false);
 
  // Priority queue to store vertices and their distances
  let pq = [];
  pq.push([P, P]);
  dist[P] = P;
 
  while (pq.length > 0) {
    // Get the vertex with the maximum minimum value
    let [dis, u] = pq.pop();
 
    // If the vertex is already visited, continue to the next iteration
    if (vis[u]) {
      continue;
    }
 
    // Mark the vertex as visited
    vis[u] = true;
 
    // Update the maximum minimum value for the neighbours
    for (let v of adj[u]) {
      // Calculate the maximum minimum value for the neighbour
      let d = Math.min(dis, v);
      if (dist[v] < d) {
        // If the neighbor's current maximum minimum value is smaller than the calculated value, update it
        dist[v] = d;
        pq.push([d, v]);
      }
    }
  }
 
  // Count the number of vertices with maximum minimum values
  let count = 0;
  for (let i = 1; i <= N; i++) {
    if (i <= dist[i]) {
      count++;
    }
  }
 
  return count;
}
 
function solve(N, M, P, edges) {
  // Create adjacency list representation of the graph
  let adj = new Array(N + 1).fill().map(() => []);
 
  for (let edge of edges) {
    let [u, v] = edge;
    adj[u].push(v);
    adj[v].push(u);
  }
 
  // Call Dijkstra's algorithm to find the maximum minimum values
  let filledVertices = Dijkstra(N, P, adj);
 
  // Output the result
  console.log("Number of filled vertices are: " + filledVertices);
}
 
// Example input
let N = 4,
  M = 4,
  P = 4;
let edges = [
  [1, 3],
  [1, 4],
  [2, 3],
  [2, 4]
];
 
// Solve the problem
solve(N, M, P, edges);
 
// This code is contributed by Tapesh(tapeshda420)

Output

Number of filled vertices are: 3

Time Complexity: O(N*logN)
Auxiliary Space: O(N)


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Inserting Elements in an Array | Array Operations Inserting Elements in an Array | Array Operations
Count unvisited leaves after Frog Jumps Count unvisited leaves after Frog Jumps
Minimum number of operations to make all letters in the string equal Minimum number of operations to make all letters in the string equal
Path queries through restricted weighted edges Path queries through restricted weighted edges
Find the character which remains in the end Find the character which remains in the end

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje