Depth-first search is a fundamental graph traversal algorithm. A grasp of recursion is beneficial before learning DFS.

Implementing Graph Traversal with DFS

Contagion Spread Problem

Problem Statemnet A simulation involves N entities, each existing at a unique coordinate point. These entities function independently. However, a contagion originates from the first entity. If an entity is infected, all other entities within a distance D of that infected entity will also become infected. Given the coordinates of all N entities and the contagion radius D, determine which entities will ultimately become infected.

Input Format The first line contains a positive integer N (1 < N ≤ 10^3). The next N lines each contain two real numbers X_i and Y_i (-10^3 ≤ X_i, Y_i ≤ 10^3), representing the coordinates of the i-th entity. The first entity is the origin of the contagion. The final line contains a positive integer D (1 <= D <= 10^3), the infection radius.

Output Format Print N lines. The i-th line should contain 1 if the i-th entity is infected, or 0 if it is not.

Sample Input

5
0 0
1 1
0 1
1 0
2 2
1

Sample Output

1
1
1
1
0

Solution Analysis

The contagion spreads from infected entities to all uninfected entities within distence D. This defines a graph where nodes are entities, and edges exist between nodes whose Euclidean distance is ≤ D. The task is to find all nodes reachable from the source node (entity 1) via these edges, wich is a graph traversal problem.

We can model infection status with an array infected[], where infected[i]=1 marks entity i as infected. The DFS function explores from a currently infected node:

private static void spreadInfection(int currentNode) {
    infected[currentNode] = 1;
    for (int targetNode = 1; targetNode <= totalNodes; targetNode++) {
        if (infected[targetNode] == 0 && distanceBetween(currentNode, targetNode) <= infectionRadius) {
            spreadInfection(targetNode);
        }
    }
}

In spreadInfection(currentNode), we mark the currentNode as infected. The loop checks all other entities. If an entity is not yet infected (infected[targetNode]==0) and is within the infection radius of the current node, it becomes a new infection source, and we recursively call spreadInfection(targetNode). The check infected[targetNode]==0 prevents infinite recursion and repeated processing of already infected nodes.

The distance calculation uses the standard Euclidean formula:

private static double distanceBetween(int nodeA, int nodeB) {
    double deltaX = coordX[nodeA] - coordX[nodeB];
    double deltaY = coordY[nodeA] - coordY[nodeB];
    return Math.sqrt(deltaX * deltaX + deltaY * deltaY);
}

After initiating DFS from the first entity, the infected array indicates the final state of all entities.

Complete Solution Code

import java.util.Scanner;

public class ContagionDFS {
    static int totalNodes, infectionRadius;
    static double[] coordX, coordY;
    static int[] infected;

    public static void main(String[] args) {
        Scanner inputReader = new Scanner(System.in);
        totalNodes = inputReader.nextInt();
        coordX = new double[totalNodes + 1];
        coordY = new double[totalNodes + 1];
        infected = new int[totalNodes + 1];

        for (int i = 1; i <= totalNodes; i++) {
            coordX[i] = inputReader.nextDouble();
            coordY[i] = inputReader.nextDouble();
        }
        infectionRadius = inputReader.nextInt();
        inputReader.close();

        spreadInfection(1); // Start DFS from the source entity

        for (int i = 1; i <= totalNodes; i++) {
            System.out.println(infected[i]);
        }
    }

    private static void spreadInfection(int currentNode) {
        infected[currentNode] = 1;
        for (int targetNode = 1; targetNode <= totalNodes; targetNode++) {
            if (infected[targetNode] == 0 && distanceBetween(currentNode, targetNode) <= infectionRadius) {
                spreadInfection(targetNode);
            }
        }
    }

    private static double distanceBetween(int nodeA, int nodeB) {
        double diffX = coordX[nodeA] - coordX[nodeB];
        double diffY = coordY[nodeA] - coordY[nodeB];
        return Math.sqrt(diffX * diffX + diffY * diffY);
    }
}