Session 48: Graph 5 Topological Sort

Original Session

Date: 09 March 2025

Topic: Graph

Concept: Topological Sort

Concept: Indegree, outdegree

Programs

207. Course Schedule

leetcode here

public boolean canFinish(int numCourses, int[][] prerequisites) {
        
        int[] indegree = new int[numCourses];
        List<List<Integer>> graph = new ArrayList();
        for (int i=0; i<numCourses; i++) {
            graph.add(new ArrayList());
        }

        for (int i=0; i<prerequisites.length; i++) {

            int u = prerequisites[i][0];
            int v = prerequisites[i][1];

            graph.get(v).add(u);
            indegree[u]++;
        }

        Queue<Integer> q = new LinkedList();
        for (int i=0; i<numCourses; i++) {

            if (indegree[i] == 0) {
                q.add(i);
            }
        }

        int count = 0;
        while (!q.isEmpty()) {

            int x = q.remove();
            count ++;

            for (int i: graph.get(x)) {

                indegree[i]--;
                if (indegree[i] == 0) {
                    q.add(i);
                }
            }
        }

        return count == numCourses;
    }

210. Course Schedule II
1. leetcode here
```
// write using above code
```

269. Alien Dictionary

leetcode here

Question From Leetcode Premium.

There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you.
You are given a list of strings words from the alien language's dictionary. Now it is claimed that the strings in words are
by the rules of this new language.
If this claim is incorrect, and the given arrangement of string in words cannot correspond to any order of letters, return "".
Otherwise, return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there are multiple solutions, return any of them.
Example 1:
Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
Example 2:
Input: words = ["z","x"]
Output: "zx"
Example 3:
Input: words = ["z","x","z"]
Output: ""
Explanation: The order is invalid, so return"".
Constraints:
1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists of only lowercase English letters.

From ChatGPT

public String alienOrder(String[] words) {
        
        int[] indegree = new int[26];
        List<Integer>[] graph = new List[26];

        // Initialize indegree and adjacency list
        for (int i = 0; i < 26; i++) {
            indegree[i] = -1;
            graph[i] = new ArrayList<>();
        }

        // Mark characters that appear in words
        for (String word : words) {
            for (char c : word.toCharArray()) {
                indegree[c - 'a'] = 0;
            }
        }

        // Build graph from words
        for (int i = 0; i < words.length - 1; i++) {
            String first = words[i];
            String second = words[i + 1];

            // Invalid case: if first word is a prefix of second but longer
            if (first.length() > second.length() && first.startsWith(second)) {
                return "";
            }

            // Compare characters to find the first differing character
            for (int j = 0; j < Math.min(first.length(), second.length()); j++) {
                if (first.charAt(j) != second.charAt(j)) {
                    graph[first.charAt(j) - 'a'].add(second.charAt(j) - 'a');
                    indegree[second.charAt(j) - 'a']++;
                    break;
                }
            }
        }

        // Topological sorting (Kahn's algorithm)
        Queue<Integer> queue = new LinkedList<>();
        StringBuilder order = new StringBuilder();

        // Add characters with indegree 0 to queue
        for (int i = 0; i < 26; i++) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            order.append((char) (curr + 'a'));

            for (int neighbor : graph[curr]) {
                if (--indegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }

        // If order length is less than the unique characters in words, return ""
        for (int i : indegree) {
            if (i > 0) return "";
        }

        return order.toString();
    }

2115. Find All Possible Recipes from Given Supplies

leetcode here

public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        
        Set<String> availableSupplies = new HashSet<>(Arrays.asList(supplies));
        Map<String, Integer> recipeToIndex = new HashMap<>();
        Map<String, List<String>> dependencyGraph = new HashMap<>();
        int n = recipes.length;

        // Create recipe to index mapping
        for (int i = 0; i < n; i++) {
            recipeToIndex.put(recipes[i], i);
        }

        // Count of non-supply ingredients needed for each recipe
        int[] inDegree = new int[n];

        // Build dependency graph
        for (int i = 0; i < n; i++) {
            for (String ingredient : ingredients.get(i)) {
                if (!availableSupplies.contains(ingredient)) {
                    // Add edge: ingredient -> recipe
                    dependencyGraph.computeIfAbsent(ingredient, k -> new ArrayList<>()).add(recipes[i]);
                    inDegree[i]++;
                }
            }
        }

        // Start with recipes that only need supplies
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        // Process recipes in topological order
        List<String> createdRecipes = new ArrayList<>();
        while (!queue.isEmpty()) {
            int i = queue.poll();
            String recipe = recipes[i];
            createdRecipes.add(recipe);

            // Skip if no recipes depend on this one
            if (!dependencyGraph.containsKey(recipe)) continue;

            // Update recipes that depend on the current recipe
            for (String dependentRecipe : dependencyGraph.get(recipe)) {
                if (--inDegree[recipeToIndex.get(dependentRecipe)] == 0) {
                    queue.add(recipeToIndex.get(dependentRecipe));
                }
            }
        }

        return createdRecipes;
    }