Java Coding Test Course, Gift Delivery

In the process of preparing for coding tests, you will encounter various algorithm problems. In this course, we will take a detailed look at understanding and solving the problem titled ‘Gift Distribution.’ This problem has a complex combination of graph exploration and distribution elements, making it a frequently appearing type in coding tests.

Problem Description

One day, N friends gathered to exchange gifts with each other. The friends give gifts according to specific rules, where each friend has a list of friends to whom they can give gifts. The direction and number of gifts exchanged are fixed, and every friend must receive exactly one gift.

Our goal is to count all possible scenarios and find the total number of ways the friends can exchange gifts with each other. The input for this problem is the number of friends N and the list of indices of friends each friend can give gifts to.

Example Problem

    Input:
    4
    1 2
    2 3
    3 4
    4 1

    Output:
    4

In the above example, there are 4 ways for 4 friends to mutually exchange gifts. Finding these cases is our main objective.

Algorithm Design

To solve this problem effectively, it is beneficial to use graph theory. By viewing friends as vertices and the relationships of giving gifts as edges, this problem is transformed into the form of a directed graph. Now, we need to find the strongly connected components in this graph. This will allow us to calculate the number of ways to ensure that all friends exchange gifts.

The algorithm we will use is as follows:

  • Construct the graph.
  • Find the Strongly Connected Components (SCC).
  • Calculate the number of possible gift-giving ways for each connected component.
  • Multiply the number of ways for each connected component to derive the final answer.

Implementation

Now, let’s implement this algorithm using Java. Here is the code:

    import java.util.*;

    public class GiftDistribution {
        static int N;
        static List> graph = new ArrayList<>();
        static boolean[] visited;
        static Stack stack = new Stack<>();
        static List> scc = new ArrayList<>();

        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            
            // Read input
            N = sc.nextInt();
            for (int i = 0; i < N; i++) {
                graph.add(new ArrayList<>());
                int count = sc.nextInt();
                for (int j = 0; j < count; j++) {
                    graph.get(i).add(sc.nextInt() - 1);
                }
            }

            visited = new boolean[N];
            // Perform DFS on all vertices
            for (int i = 0; i < N; i++) {
                if (!visited[i]) {
                    dfs(i);
                }
            }

            // Create reverse graph
            List> reverseGraph = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                reverseGraph.add(new ArrayList<>());
            }
            for (int i = 0; i < N; i++) {
                for (int neighbor : graph.get(i)) {
                    reverseGraph.get(neighbor).add(i);
                }
            }

            Arrays.fill(visited, false);
            // Find SCC
            while (!stack.isEmpty()) {
                int v = stack.pop();
                if (!visited[v]) {
                    List component = new ArrayList<>();
                    reverseDfs(v, component, reverseGraph);
                    scc.add(component);
                }
            }

            // Calculate the number of cases
            int result = 1;
            for (List component : scc) {
                result *= factorial(component.size());
            }
            System.out.println(result);
        }

        static void dfs(int v) {
            visited[v] = true;
            for (int neighbor : graph.get(v)) {
                if (!visited[neighbor]) {
                    dfs(neighbor);
                }
            }
            stack.push(v);
        }

        static void reverseDfs(int v, List component, List> reverseGraph) {
            visited[v] = true;
            component.add(v);
            for (int neighbor : reverseGraph.get(v)) {
                if (!visited[neighbor]) {
                    reverseDfs(neighbor, component, reverseGraph);
                }
            }
        }

        static int factorial(int n) {
            int fact = 1;
            for (int i = 1; i <= n; i++) {
                fact *= i;
            }
            return fact;
        }
    }

Code Explanation

The code consists of the following processes:

  1. Input processing for the graph: Takes the list of friends each friend can give gifts to and constructs the graph.
  2. Stack creation using DFS: Performs depth-first search on all vertices and adds them to the stack after visiting.
  3. Creating a transpose graph: Generates a transpose graph by reversing the edges of the original graph.
  4. Finding SCC: Pops vertices from the stack one at a time and finds SCC using the transpose graph.
  5. Calculating the number of cases: Computes the factorial for the size of each SCC to derive the final result.

Complexity Analysis

The time complexity of this algorithm is O(N + E). Here, N indicates the number of nodes, and E indicates the number of edges. Additionally, the space complexity is also O(N + E), as space is required to store the graph.

Conclusion

In this course, we explored how to solve the ‘Gift Distribution’ problem. We closely examined the implementation process of the algorithm and the complexity analysis. These types of problems can often be encountered not only in coding tests but also in actual projects; therefore, deepening your understanding of graph theory and algorithms is essential.

Based on what we covered here, I encourage you to practice solving exercises to build your skills. In the next course, we will return with another valuable problem!