This Java code implements a directed graph structure to represent...

April 3, 2025 at 10:19 PM

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
import java.lang.reflect.Array;
import javax.sound.sampled.BooleanControl;
import javax.swing.text.Position;

class Result {
    public class Vertex {
        public int courseNum;
        public ArrayList<Edge> outgoing, incoming;
            
        public Vertex(int courseNum) {
            this.courseNum = courseNum;
            incoming = new ArrayList<>();
            outgoing = new ArrayList<>();
        }
    }
        
    public class Edge {
        public Vertex[] endpoints;
            
        public Edge(Vertex prerequisite, Vertex course) {
            endpoints = new Vertex[]{prerequisite, course};
        }
    }
        
    private ArrayList<Vertex> vertices = new ArrayList<>();
    private ArrayList<Edge> edges = new ArrayList<>();
        
    public Vertex insertVertex(int courseNum) {
        Vertex newVertex = new Vertex(courseNum);
        vertices.add(newVertex);
        return newVertex;
    }
        
    public Edge insertEdge(Vertex prereq, Vertex course) {
        Edge newEdge = new Edge(prereq, course);
        prereq.outgoing.add(newEdge);
        course.incoming.add(newEdge);
        edges.add(newEdge);
        return newEdge;
    }
    
    private Vertex head;
    private int numCourses;
    
    public Result(int numCourses) {
        Vertex newVertex = new Vertex(0);
        this.head = newVertex;
        for (int i = 1; i < numCourses; i++) {
            insertVertex(i);
        }
        this.numCourses = numCourses;
    }
    
    public Vertex opposite(Vertex v, Edge e){
        if(e.endpoints[0] == v) return e.endpoints[1];
        else if(e.endpoints[1] == v) return e.endpoints[0];
        else throw new IllegalArgumentException("v is not incident to this edge");
    }
    
    

    /*
     * Complete the 'addPrereq' function below.
     *
     * The function accepts following parameters:
     *  1. INTEGER prereq
     *  2. INTEGER course
     */

    // Add prerequisite
    public void addPrereq(int prereq, int course) {
        Vertex prereqPtr = vertices.get(prereq);
        Vertex coursePtr = vertices.get(course);
        insertEdge(prereqPtr, coursePtr);
    }

  
    // Complete the 'isPossible' function below.
    public boolean isPossible() {
        ArrayList<Boolean> possible = new ArrayList<Boolean>();
        for (Vertex v: vertices) {
            possible.add(CycleDetectionWrapper(v));
        }
        if (possible.contains(false)) return false;
        else return true;
    }
    
    public boolean CycleDetectionWrapper(Vertex v){
        HashMap<Vertex,Edge> record = new HashMap<>();
        HashMap<Vertex,Edge> ancestors = new HashMap<>();
        record.put(v,null);
        ancestors.put(v,null);
        
        return CycleDetection(record,v,ancestors);
    }
    
    public boolean CycleDetection(HashMap<Vertex,Edge> record, Vertex u, HashMap<Vertex,Edge> ancestors){
        for (Edge e: u.outgoing){
            Vertex v = opposite(u, e);
            if(ancestors.containsKey(v)) return true;
            if(record.containsKey(v)==false){
                record.put(v,e);
                ancestors.put(v,null);
                if (CycleDetection(record,v,ancestors)==true) return true;
                ancestors.remove(v);
            }
        }
        return false;
    }
  
}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        int numCourses = Integer.parseInt(firstMultipleInput[0]);
        int numPrereqs = Integer.parseInt(firstMultipleInput[1]);

        Result result = new Result(numCourses);
        IntStream.range(0, numPrereqs).forEach(numPrereqsItr -> {
            try {
                String[] secondMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
                int prereq = Integer.parseInt(secondMultipleInput[0]);
                int course = Integer.parseInt(secondMultipleInput[1]);
               
                result.addPrereq(prereq, course);
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });
        if (result.isPossible())
            System.out.println("possible");
        else
            System.out.println("IMPOSSIBLE");

        bufferedReader.close();
    }
}

This Java code implements a directed graph structure to represent a course prerequisite system and determines whether all courses can be completed without any prerequisite cycle (i.e., whether it's possible to do a valid topological ordering of courses). Here's a breakdown of the key parts of the code:

1. Graph Representation

The course prerequisite system is represented as a directed graph:

Vertices: Represent courses (Vertex class), where each Vertex has:
- courseNum: Represents the course number.
- incoming: List of incoming edges (prerequisites for this course).
- outgoing: List of outgoing edges (courses this course is a prerequisite for).
Edges: Represent prerequisites (Edge class):
- Each Edge connects two Vertex instances: a prerequisite course and the dependent course.

The graph data structures include:

vertices: List of all course vertices.
edges: List of all prerequisite edges.

2. Key Methods

insertVertex: Adds a new course (Vertex) to the graph.
insertEdge: Adds a directed edge (prerequisite relationship) between two courses.
addPrereq: Helper function used to add prerequisites based on input.

3. Cycle Detection

The isPossible method determines if it's possible to complete all courses. It does so by detecting cycles in the graph, as a cycle indicates a prerequisite loop (which makes it impossible to complete the courses).

Cycle Detection Implementation:
- Uses Depth-First Search (DFS) via CycleDetectionWrapper and CycleDetection.
- Maintains a set of record (visited vertices) and ancestors (currently explored path to check for cycles).
- If a cycle is detected (a vertex already exists in ancestors), the cycle detection returns true (cycle exists, so the schedule is not possible).

4. Result Output

The program reads input:

numCourses: Total number of courses.
numPrereqs: Total number of prerequisite relationships.
A series of prerequisite pairs (prereq, course), representing the course dependency from prereq to course.

It constructs the graph, checks for cycles using isPossible, and outputs:

"possible": If there are no cycles, and courses can be completed.
"IMPOSSIBLE": If there's a cycle, making it impossible to complete the courses.

Example Workflow

Input:

4 courses.
3 prerequisites:
- Course 1 requires course 0.
- Course 2 requires course 1.
- Course 0 requires course 2 (cycle introduced).

The program constructs a graph with these courses and prerequisites. The isPossible method detects a cycle (0 → 1 → 2 → 0). Thus, it prints:

IMPOSSIBLE

Input:

4 2
1 0
2 1

This input has no cycle. The courses can be completed (e.g., order: 0 → 1 → 2 → 3), so it prints:

possible

What the Code Does:

Models a prerequisite system as a directed graph.
Attempts to detect cycles in the graph to determine if the courses can be scheduled in a valid order.
Outputs whether it is "possible" or "IMPOSSIBLE" to complete the courses based on the presence of cycles.

Generate your own explanations

Download our vscode extension

Read other generated explanations

Built by @thebuilderjr