java - 常用食材组合

我正在研究以下问题：
假设你有一个菜品清单，每个菜品都与
配料表用常用的配料把菜组在一起。
例如：
输入：

"Pasta" -> ["Tomato Sauce", "Onions", "Garlic"]
"Chicken Curry" --> ["Chicken", "Curry Sauce"]
"Fried Rice" --> ["Rice", "Onions", "Nuts"]
"Salad" --> ["Spinach", "Nuts"]
"Sandwich" --> ["Cheese", "Bread"]
"Quesadilla" --> ["Chicken", "Cheese"]

输出：

("Pasta", "Fried Rice")
("Fried Rice, "Salad")
("Chicken Curry", "Quesadilla")
("Sandwich", "Quesadilla")

时间和空间的复杂性又是什么呢？
我想出了下面的代码。有没有更好的方法来解决这个问题它看起来像是图论中的连通成分。

public static void main(String[] args) {
    List<String> ing1 = Arrays.asList("Tomato Sauce", "Onions", "Garlic");
    List<String> ing2 = Arrays.asList("Chicken", "Curry Sauce");
    List<String> ing3 = Arrays.asList("Rice", "Onions", "Nuts");
    List<String> ing4 = Arrays.asList("Spinach", "Nuts");
    List<String> ing5 = Arrays.asList("Cheese", "Bread");
    List<String> ing6 = Arrays.asList("Chicken", "Cheese");

    Map<String, List<String>> map = new HashMap<>();
    map.put("Pasta", ing1);
    map.put("Chicken Curry", ing2);
    map.put("Fried Rice", ing3);
    map.put("Salad", ing4);
    map.put("Sandwich", ing5);
    map.put("Quesadilla", ing6);

    System.out.println(group(map));
}

private static List<List<String>> group(Map<String, List<String>> map) {
    List<List<String>> output = new ArrayList<>();

    if (map == null || map.isEmpty()) {
        return output;
    }

    Map<String, List<String>> holder = new HashMap<>();

    for (Map.Entry<String, List<String>> entry : map.entrySet()) {
        String key = entry.getKey();
        List<String> value = entry.getValue();
        for (String v : value) {
            if (!holder.containsKey(v)) {
                holder.put(v, new ArrayList<String>());
            }
            holder.get(v).add(key);
        }
    }
    return new ArrayList<List<String>>(holder.values());
}

最佳答案

我们可以使用图论对这种方法进行实际的复杂性估计。一个“连接成分”的方法将具有O(|V| + |E|)复杂性，其中V是所有配料和菜肴的集合，E是包含所有关系的集合(a, b)每一个a是一个菜肴，b是碟子b的一个配料。（即，假设您将此图存储在邻接列表中，而不是存储在邻接矩阵中）
在任何需要找出每道菜的所有成分才能找到结果的算法中，你必须调查每道菜及其所有成分。这将导致需要G = (V, E)时间的调查（即遍历），这意味着没有一种算法比您的方法更好。