Topological Sort Pattern

import java.util.*;
public class CourseSchedule {
    // Check if all courses can be finished
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        // Build graph and in-degree array
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph.put(i, new ArrayList<>());
        }
        for (int[] prereq : prerequisites) {
            int course = prereq[0];
            int prerequisite = prereq[1];
            graph.get(prerequisite).add(course);
            inDegree[course]++;
        }
        // Queue for courses with no prerequisites
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        int coursesCompleted = 0;
        // Process courses
        while (!queue.isEmpty()) {
            int course = queue.poll();
            coursesCompleted++;
            // Reduce in-degree of dependent courses
            for (int dependent : graph.get(course)) {
                inDegree[dependent]--;
                if (inDegree[dependent] == 0) {
                    queue.offer(dependent);
                }
            }
        }
        return coursesCompleted == numCourses;
    }
    public static void main(String[] args) {
        int numCourses = 4;
        int[][] prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
        System.out.println("Can finish: " + canFinish(numCourses, prerequisites));
        // Output: true
        // Valid order: 0 → 1 → 2 → 3
        prerequisites = new int[][]{{1, 0}, {0, 1}};
        System.out.println("Can finish (cycle): " + canFinish(2, prerequisites));
        // Output: false (0 needs 1, 1 needs 0 - cycle!)
    }
}

import java.util.*;
public class CourseScheduleII {
    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        // Build graph and in-degree
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph.put(i, new ArrayList<>());
        }
        for (int[] prereq : prerequisites) {
            int course = prereq[0];
            int prerequisite = prereq[1];
            graph.get(prerequisite).add(course);
            inDegree[course]++;
        }
        // Queue for sources (in-degree 0)
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        int[] order = new int[numCourses];
        int index = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            order[index++] = course;
            for (int dependent : graph.get(course)) {
                inDegree[dependent]--;
                if (inDegree[dependent] == 0) {
                    queue.offer(dependent);
                }
            }
        }
        // If couldn't complete all courses, return empty
        return index == numCourses ? order : new int[0];
    }
    public static void main(String[] args) {
        int numCourses = 4;
        int[][] prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
        int[] order = findOrder(numCourses, prerequisites);
        System.out.print("Course order: ");
        for (int course : order) {
            System.out.print(course + " ");
        }
        System.out.println();
        // Output: 0 1 2 3 (or 0 2 1 3 - both valid)
    }
}

import java.util.*;
public class AlienDictionary {
    public static String alienOrder(String[] words) {
        // Build graph
        Map<Character, Set<Character>> graph = new HashMap<>();
        Map<Character, Integer> inDegree = new HashMap<>();
        // Initialize graph
        for (String word : words) {
            for (char c : word.toCharArray()) {
                graph.putIfAbsent(c, new HashSet<>());
                inDegree.putIfAbsent(c, 0);
            }
        }
        // Build edges by comparing adjacent words
        for (int i = 0; i < words.length - 1; i++) {
            String word1 = words[i];
            String word2 = words[i + 1];
            int minLen = Math.min(word1.length(), word2.length());
            // Find first different character
            for (int j = 0; j < minLen; j++) {
                char c1 = word1.charAt(j);
                char c2 = word2.charAt(j);
                if (c1 != c2) {
                    // c1 comes before c2
                    if (!graph.get(c1).contains(c2)) {
                        graph.get(c1).add(c2);
                        inDegree.put(c2, inDegree.get(c2) + 1);
                    }
                    break;
                }
            }
            // Invalid case: word1 is prefix but comes after
            if (word1.length() > word2.length() &&
                word1.startsWith(word2)) {
                return "";
            }
        }
        // Topological sort
        Queue<Character> queue = new LinkedList<>();
        for (char c : inDegree.keySet()) {
            if (inDegree.get(c) == 0) {
                queue.offer(c);
            }
        }
        StringBuilder result = new StringBuilder();
        while (!queue.isEmpty()) {
            char c = queue.poll();
            result.append(c);
            for (char next : graph.get(c)) {
                inDegree.put(next, inDegree.get(next) - 1);
                if (inDegree.get(next) == 0) {
                    queue.offer(next);
                }
            }
        }
        return result.length() == inDegree.size() ? result.toString() : "";
    }
    public static void main(String[] args) {
        String[] words = {"wrt", "wrf", "er", "ett", "rftt"};
        System.out.println("Alien order: " + alienOrder(words));
        // Output: "wertf"
        // From comparisons: w<e, t<f, r<t
    }
}