Swift Coding Test Course, I Don’t Want to Be a Liar

Problem Description

Recently, a participant attended a wedding where he was elected as a slacker. However, there were 100 friends at the wedding whom he did not want to invite. These friends are planning to introduce others as their friends by lying.

Each friend can claim, ‘I know A and B’, about specific individuals. Your task is to verify all the lies and determine whether two friends know the same person.

The given input includes the number of friends and the lying information of each friend. Based on the input information, you need to determine which friends are lying.

Input Example

                5
                1 2
                2 3
                3 4
                4 5
                1 5
            

The first line contains the number of friends N, and the following N lines provide the numbers of the friends each friend knows.

Output Example

                Yes
            

If the two friends know each other, print ‘Yes’; otherwise, print ‘No’.

Approach to the Problem

To solve this problem, we can use graph search algorithms. We represent each friend as a vertex and their relationships as edges to form a graph. We can use search methods such as DFS or BFS to check if two friends know each other.

The basic approach is to store friend relationships in a list and conduct a graph search for the given two friends.

Code Implementation

Below is the implementation of the code in Swift.

                
                import Foundation

                func canKnowEachOther(N: Int, friendships: [(Int, Int)], friendA: Int, friendB: Int) -> String {
                    // Initialize graph
                    var graph = Array(repeating: [Int](), count: N + 1)

                    // Store friendships
                    for (a, b) in friendships {
                        graph[a].append(b)
                        graph[b].append(a)
                    }

                    // Initialize BFS
                    var queue = [friendA]
                    var visited = Array(repeating: false, count: N + 1)
                    visited[friendA] = true

                    while !queue.isEmpty {
                        let current = queue.removeFirst()

                        // Did we find friend B?
                        if current == friendB {
                            return "Yes"
                        }

                        for neighbor in graph[current] {
                            if !visited[neighbor] {
                                visited[neighbor] = true
                                queue.append(neighbor)
                            }
                        }
                    }

                    return "No"
                }

                // Input example
                let N = 5
                let friendships = [(1, 2), (2, 3), (3, 4), (4, 5), (1, 5)]
                let result = canKnowEachOther(N: N, friendships: friendships, friendA: 1, friendB: 5)
                print(result) // "Yes"
                
            

Code Explanation

The above code operates as follows:

• Graph Initialization: Initializes the graph in the form of an adjacency list based on the input friendships.
• BFS Search: Starts from the given friend A and executes a BFS to check if we reach friend B. Already visited friends are tracked to avoid revisiting.
• Return Result: If friend B is found, it returns “Yes”; if not found after finishing the search, it returns “No”.

Additional Considerations

The method for solving this problem is quite intuitive as it involves basic DFS/BFS searching. However, if the scope of the problem increases, we may need to explore more efficient methods. For example, if the number of friends becomes large, applying the Union-Find algorithm instead of DFS may be performance advantageous.

If more complex relationships or random configurations of data are provided, various techniques (e.g., Dynamic Programming options) can be utilized to address them. It is crucial to consider worst-case time and space complexity when selecting the algorithm design.