Java Coding Test Course, Understanding Friend Relationships

Hello, everyone! In this post, we will cover a problem that frequently appears in coding tests, Identifying Friend Relationships. The problem we will introduce is a graph traversal problem that presents a task of analyzing friend relationships and calculating the number of friends satisfying certain conditions.

Problem Description

You have hosted a party with N friends. Each friend is connected to others through friendship. Friend relationships are bidirectional, and each friend A and friend B can only check friends among their friends. In other words, a friend of friend A is only a friend directly connected to A. Your mission is to count how many ‘2nd degree friends’ you can find among a specific friend’s friends.

Problem Definition

    Input:
    - N (1 ≤ N ≤ 100) : Number of friends
    - M (1 ≤ M ≤ 10^4) : Number of pairs of friend relationships
    - M pairs (A, B): Two friends A and B.

    Output:
    - X: Number of 2nd degree friends of a specific friend.

    You need to count the 2nd degree friends of a specific friend K.

Sample Input

    6 5
    1 2
    2 3
    1 4
    4 5
    5 6
    1

Sample Output

    2

Approach to the Problem

To solve this problem, we need to use a graph data structure to represent friend relationships. We will create an adjacency list for this purpose. After that, we need to find 2nd degree friends using either breadth-first search (BFS) or depth-first search (DFS). Each friend in the graph can be viewed as a vertex, while friend relationships are edges.

Step-by-Step Approach

  1. Read the input values and create an adjacency list based on the connection information of the friend relationships.
  2. Use BFS or DFS based on the specific friend K to explore the relationships of friends of friends.
  3. During the exploration process, exclude friends directly connected to K, and use a set to prevent duplicates among friends of friends.
  4. Finally, output the size of the set.

Implementation Code (Java)

    import java.util.*;

    public class FriendRelations {
        static List[] graph;
        static Set friendsOfFriends;

        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int N = scanner.nextInt();
            int M = scanner.nextInt();
            graph = new ArrayList[N + 1];
            for (int i = 1; i <= N; i++) {
                graph[i] = new ArrayList<>();
            }

            for (int i = 0; i < M; i++) {
                int A = scanner.nextInt();
                int B = scanner.nextInt();
                graph[A].add(B);
                graph[B].add(A);
            }

            int K = scanner.nextInt();
            friendsOfFriends = new HashSet<>();

            for (int friend : graph[K]) {
                for (int f2 : graph[friend]) {
                    if (f2 != K && !graph[K].contains(f2)) {
                        friendsOfFriends.add(f2);
                    }
                }
            }
            System.out.println(friendsOfFriends.size());
            scanner.close();
        }
    }

Code Explanation

The first part of the code defines the graph to store friend relationships and initializes the relationship of friends in the adjacency list format through input values. It then explores the friends of the specified friend K and adds them to a set to remove duplicates. Finally, it calculates the number of 2nd degree friends of K using the size of the set.

Code Execution

Now let’s execute the code to see the results. Using the above sample input, the outcome of the code will be ‘2’. This means that the specific friend K has a total of 2 second degree friends.

Conclusion

This problem serves as a good exercise in utilizing basic concepts of graph theory. The theory of friend relationships often appears in many coding interviews, and by solving such problems, you can further enhance your knowledge related to graph traversal.

In the next post, we will tackle another useful algorithm problem and its solution process. If you have any questions, please leave a comment!