Sort Items by Groups Respecting Dependencies

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
using namespace std;

vector<int> topSort(vector<vector<int>>& graph, vector<int>& indegree) {
    queue<int> q;
    vector<int> result;
    
    for (int i = 0; i < indegree.size(); i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        result.push_back(node);
        
        for (int neighbor : graph[node]) {
            indegree[neighbor]--;
            if (indegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }
    
    return result;
}

vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
    // Assign unique group IDs to items without groups
    int groupId = m;
    for (int i = 0; i < n; i++) {
        if (group[i] == -1) {
            group[i] = groupId++;
        }
    }
    
    // Build group graph and item graph
    vector<vector<int>> groupGraph(groupId);
    vector<int> groupIndegree(groupId, 0);
    vector<vector<int>> itemGraph(n);
    vector<int> itemIndegree(n, 0);
    
    for (int i = 0; i < n; i++) {
        for (int prev : beforeItems[i]) {
            // Item dependency
            itemGraph[prev].push_back(i);
            itemIndegree[i]++;
            
            // Group dependency (if different groups)
            if (group[prev] != group[i]) {
                groupGraph[group[prev]].push_back(group[i]);
                groupIndegree[group[i]]++;
            }
        }
    }
    
    // Topological sort for groups
    vector<int> groupOrder = topSort(groupGraph, groupIndegree);
    if (groupOrder.size() != groupId) {
        return {}; // Cycle detected
    }
    
    // Topological sort for items
    vector<int> itemOrder = topSort(itemGraph, itemIndegree);
    if (itemOrder.size() != n) {
        return {}; // Cycle detected
    }
    
    // Group items by their groups
    unordered_map<int, vector<int>> groupToItems;
    for (int item : itemOrder) {
        groupToItems[group[item]].push_back(item);
    }
    
    // Build final result respecting group order
    vector<int> result;
    for (int g : groupOrder) {
        for (int item : groupToItems[g]) {
            result.push_back(item);
        }
    }
    
    return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

func topSort(graph [][]int, indegree []int) []int {
    var queue []int
    var result []int
    
    for i, deg := range indegree {
        if deg == 0 {
            queue = append(queue, i)
        }
    }
    
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        result = append(result, node)
        
        for _, neighbor := range graph[node] {
            indegree[neighbor]--
            if indegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }
    
    return result
}

func sortItems(n int, m int, group []int, beforeItems [][]int) []int {
    // Assign unique group IDs
    groupId := m
    for i := 0; i < n; i++ {
        if group[i] == -1 {
            group[i] = groupId
            groupId++
        }
    }
    
    // Build graphs
    groupGraph := make([][]int, groupId)
    groupIndegree := make([]int, groupId)
    itemGraph := make([][]int, n)
    itemIndegree := make([]int, n)
    
    for i := 0; i < n; i++ {
        for _, prev := range beforeItems[i] {
            itemGraph[prev] = append(itemGraph[prev], i)
            itemIndegree[i]++
            
            if group[prev] != group[i] {
                groupGraph[group[prev]] = append(groupGraph[group[prev]], group[i])
                groupIndegree[group[i]]++
            }
        }
    }
    
    // Topological sorts
    groupOrder := topSort(groupGraph, groupIndegree)
    if len(groupOrder) != groupId {
        return []int{}
    }
    
    itemOrder := topSort(itemGraph, itemIndegree)
    if len(itemOrder) != n {
        return []int{}
    }
    
    // Group items
    groupToItems := make(map[int][]int)
    for _, item := range itemOrder {
        g := group[item]
        groupToItems[g] = append(groupToItems[g], item)
    }
    
    // Build result
    var result []int
    for _, g := range groupOrder {
        result = append(result, groupToItems[g]...)
    }
    
    return result
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

import java.util.*;

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        // Assign unique group IDs to items without groups
        int groupId = m;
        for (int i = 0; i < n; i++) {
            if (group[i] == -1) {
                group[i] = groupId++;
            }
        }
        
        // Build group graph and item graph
        List<List<Integer>> groupGraph = new ArrayList<>();
        int[] groupIndegree = new int[groupId];
        List<List<Integer>> itemGraph = new ArrayList<>();
        int[] itemIndegree = new int[n];
        
        for (int i = 0; i < groupId; i++) {
            groupGraph.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            itemGraph.add(new ArrayList<>());
        }
        
        for (int i = 0; i < n; i++) {
            for (int prev : beforeItems.get(i)) {
                // Item dependency
                itemGraph.get(prev).add(i);
                itemIndegree[i]++;
                
                // Group dependency
                if (group[prev] != group[i]) {
                    groupGraph.get(group[prev]).add(group[i]);
                    groupIndegree[group[i]]++;
                }
            }
        }
        
        // Topological sort for groups
        List<Integer> groupOrder = topSort(groupGraph, groupIndegree);
        if (groupOrder.size() != groupId) return new int[0];
        
        // Topological sort for items
        List<Integer> itemOrder = topSort(itemGraph, itemIndegree);
        if (itemOrder.size() != n) return new int[0];
        
        // Group items by their groups
        Map<Integer, List<Integer>> groupToItems = new HashMap<>();
        for (int item : itemOrder) {
            groupToItems.computeIfAbsent(group[item], k -> new ArrayList<>()).add(item);
        }
        
        // Build final result
        List<Integer> result = new ArrayList<>();
        for (int g : groupOrder) {
            if (groupToItems.containsKey(g)) {
                result.addAll(groupToItems.get(g));
            }
        }
        
        return result.stream().mapToInt(i -> i).toArray();
    }
    
    private List<Integer> topSort(List<List<Integer>> graph, int[] indegree) {
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result.add(node);
            
            for (int neighbor : graph.get(node)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        return result;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

import java.util.*

class Solution {
    fun sortItems(n: Int, m: Int, group: IntArray, beforeItems: List<List<Int>>): IntArray {
        // Assign unique group IDs
        var groupId = m
        for (i in 0 until n) {
            if (group[i] == -1) {
                group[i] = groupId++
            }
        }
        
        // Build graphs
        val groupGraph = Array(groupId) { mutableListOf<Int>() }
        val groupIndegree = IntArray(groupId)
        val itemGraph = Array(n) { mutableListOf<Int>() }
        val itemIndegree = IntArray(n)
        
        for (i in 0 until n) {
            for (prev in beforeItems[i]) {
                itemGraph[prev].add(i)
                itemIndegree[i]++
                
                if (group[prev] != group[i]) {
                    groupGraph[group[prev]].add(group[i])
                    groupIndegree[group[i]]++
                }
            }
        }
        
        // Topological sorts
        val groupOrder = topSort(groupGraph.map { it.toList() }, groupIndegree)
        if (groupOrder.size != groupId) return intArrayOf()
        
        val itemOrder = topSort(itemGraph.map { it.toList() }, itemIndegree)
        if (itemOrder.size != n) return intArrayOf()
        
        // Group items
        val groupToItems = mutableMapOf<Int, MutableList<Int>>()
        for (item in itemOrder) {
            groupToItems.computeIfAbsent(group[item]) { mutableListOf() }.add(item)
        }
        
        // Build result
        val result = mutableListOf<Int>()
        for (g in groupOrder) {
            groupToItems[g]?.let { result.addAll(it) }
        }
        
        return result.toIntArray()
    }
    
    private fun topSort(graph: List<List<Int>>, indegree: IntArray): List<Int> {
        val queue: Queue<Int> = LinkedList()
        val result = mutableListOf<Int>()
        val indegreeCopy = indegree.clone()
        
        for (i in indegreeCopy.indices) {
            if (indegreeCopy[i] == 0) {
                queue.offer(i)
            }
        }
        
        while (queue.isNotEmpty()) {
            val node = queue.poll()
            result.add(node)
            
            for (neighbor in graph[node]) {
                indegreeCopy[neighbor]--
                if (indegreeCopy[neighbor] == 0) {
                    queue.offer(neighbor)
                }
            }
        }
        
        return result
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

from collections import defaultdict, deque

def sortItems(n: int, m: int, group: list[int], beforeItems: list[list[int]]) -> list[int]:
    def topological_sort(graph, indegree):
        queue = deque([i for i in range(len(indegree)) if indegree[i] == 0])
        result = []
        
        while queue:
            node = queue.popleft()
            result.append(node)
            
            for neighbor in graph[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    queue.append(neighbor)
        
        return result
    
    # Assign unique group IDs to items without groups
    group_id = m
    for i in range(n):
        if group[i] == -1:
            group[i] = group_id
            group_id += 1
    
    # Build group graph and item graph
    group_graph = defaultdict(list)
    group_indegree = [0] * group_id
    item_graph = defaultdict(list)
    item_indegree = [0] * n
    
    for i in range(n):
        for prev in beforeItems[i]:
            # Item dependency
            item_graph[prev].append(i)
            item_indegree[i] += 1
            
            # Group dependency (if different groups)
            if group[prev] != group[i]:
                group_graph[group[prev]].append(group[i])
                group_indegree[group[i]] += 1
    
    # Topological sort for groups
    group_order = topological_sort(group_graph, group_indegree)
    if len(group_order) != group_id:
        return []  # Cycle detected
    
    # Topological sort for items
    item_order = topological_sort(item_graph, item_indegree)
    if len(item_order) != n:
        return []  # Cycle detected
    
    # Group items by their groups
    group_to_items = defaultdict(list)
    for item in item_order:
        group_to_items[group[item]].append(item)
    
    # Build final result respecting group order
    result = []
    for g in group_order:
        result.extend(group_to_items[g])
    
    return result

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

use std::collections::{HashMap, VecDeque};

pub fn sort_items(n: i32, m: i32, mut group: Vec<i32>, before_items: Vec<Vec<i32>>) -> Vec<i32> {
    let n = n as usize;
    let mut group_id = m;
    
    // Assign unique group IDs
    for i in 0..n {
        if group[i] == -1 {
            group[i] = group_id;
            group_id += 1;
        }
    }
    
    let group_id = group_id as usize;
    
    // Build graphs
    let mut group_graph = vec![Vec::new(); group_id];
    let mut group_indegree = vec![0; group_id];
    let mut item_graph = vec![Vec::new(); n];
    let mut item_indegree = vec![0; n];
    
    for i in 0..n {
        for &prev in &before_items[i] {
            let prev = prev as usize;
            item_graph[prev].push(i);
            item_indegree[i] += 1;
            
            if group[prev] != group[i] {
                let prev_group = group[prev] as usize;
                let curr_group = group[i] as usize;
                group_graph[prev_group].push(curr_group);
                group_indegree[curr_group] += 1;
            }
        }
    }
    
    // Topological sorts
    let group_order = topological_sort(&group_graph, &mut group_indegree.clone());
    if group_order.len() != group_id {
        return vec![];
    }
    
    let item_order = topological_sort(&item_graph, &mut item_indegree.clone());
    if item_order.len() != n {
        return vec![];
    }
    
    // Group items
    let mut group_to_items: HashMap<usize, Vec<usize>> = HashMap::new();
    for item in item_order {
        let g = group[item] as usize;
        group_to_items.entry(g).or_insert_with(Vec::new).push(item);
    }
    
    // Build result
    let mut result = Vec::new();
    for g in group_order {
        if let Some(items) = group_to_items.get(&g) {
            result.extend(items.iter().map(|&x| x as i32));
        }
    }
    
    result
}

fn topological_sort(graph: &[Vec<usize>], indegree: &mut [i32]) -> Vec<usize> {
    let mut queue = VecDeque::new();
    let mut result = Vec::new();
    
    for (i, &deg) in indegree.iter().enumerate() {
        if deg == 0 {
            queue.push_back(i);
        }
    }
    
    while let Some(node) = queue.pop_front() {
        result.push(node);
        
        for &neighbor in &graph[node] {
            indegree[neighbor] -= 1;
            if indegree[neighbor] == 0 {
                queue.push_back(neighbor);
            }
        }
    }
    
    result
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

function sortItems(n: number, m: number, group: number[], beforeItems: number[][]): number[] {
    function topologicalSort(graph: number[][], indegree: number[]): number[] {
        const queue: number[] = [];
        const result: number[] = [];
        
        for (let i = 0; i < indegree.length; i++) {
            if (indegree[i] === 0) {
                queue.push(i);
            }
        }
        
        while (queue.length > 0) {
            const node = queue.shift()!;
            result.push(node);
            
            for (const neighbor of graph[node]) {
                indegree[neighbor]--;
                if (indegree[neighbor] === 0) {
                    queue.push(neighbor);
                }
            }
        }
        
        return result;
    }
    
    // Assign unique group IDs
    let groupId = m;
    for (let i = 0; i < n; i++) {
        if (group[i] === -1) {
            group[i] = groupId++;
        }
    }
    
    // Build graphs
    const groupGraph: number[][] = Array(groupId).fill(null).map(() => []);
    const groupIndegree: number[] = Array(groupId).fill(0);
    const itemGraph: number[][] = Array(n).fill(null).map(() => []);
    const itemIndegree: number[] = Array(n).fill(0);
    
    for (let i = 0; i < n; i++) {
        for (const prev of beforeItems[i]) {
            itemGraph[prev].push(i);
            itemIndegree[i]++;
            
            if (group[prev] !== group[i]) {
                groupGraph[group[prev]].push(group[i]);
                groupIndegree[group[i]]++;
            }
        }
    }
    
    // Topological sorts
    const groupOrder = topologicalSort(groupGraph, [...groupIndegree]);
    if (groupOrder.length !== groupId) return [];
    
    const itemOrder = topologicalSort(itemGraph, [...itemIndegree]);
    if (itemOrder.length !== n) return [];
    
    // Group items
    const groupToItems = new Map<number, number[]>();
    for (const item of itemOrder) {
        const g = group[item];
        if (!groupToItems.has(g)) {
            groupToItems.set(g, []);
        }
        groupToItems.get(g)!.push(item);
    }
    
    // Build result
    const result: number[] = [];
    for (const g of groupOrder) {
        if (groupToItems.has(g)) {
            result.push(...groupToItems.get(g)!);
        }
    }
    
    return result;
}