C++ Coding Test Course, Understanding Friend Relationships

This article discusses the process of solving an algorithm problem that identifies friendship relationships using C++. The problem involves applying graph theory based on the number of friends and their relationships to understand the friendship network. In this context, we will explore the fundamental concepts of data structures and algorithms, and examine the implementation methods in C++ in detail.

Problem Description

Problem: There are N students. Each student has the potential to have friends. The friendship relationship is bidirectional, and given the friendship relationships, implement an algorithm to determine how many friends a specific student has. Additionally, it should be able to check whether two students are friends with each other.

Input:

  • The first line contains the number of students N (1 ≤ N ≤ 1000).
  • The second line contains M (0 ≤ M ≤ N*(N-1)/2) friendship relationships.
  • Each friendship relation consists of A and B, where A is a friend of B and B is a friend of A.
  • Finally, queries are given to check the friendship relationships.

Problem Solving Process

To solve the problem, we will go through the following steps:

  1. Graph Modeling: Model the friendship relationships as a graph. The vertices represent students, and the edges represent friendship relationships.
  2. Constructing an Adjacency List: Create an adjacency list representing friends for each vertex.
  3. Count Friends: Implement a function to calculate the number of friends of a specific student.
  4. Check Friendship Relationships: Implement a function to check the friendship relationship between two students.

1. Graph Modeling

To solve the given problem, we need to first model the friendship relationships in the form of a graph. In this case, the vertices of the graph represent students, and the edges represent friendship relationships between those students.

Therefore, assuming there are N students, we can represent them with integers ranging from 0 to N-1. For example, student A can be represented as 0, and student B as 1.

2. Constructing an Adjacency List

We use an adjacency list to represent the graph. We can use a hashmap or vector where each student is a key and the list of students who are friends with that student is the value. Below is a method for constructing the adjacency list in C++: 


#include 
#include 
#include 
#include 

using namespace std;

unordered_map > friends;

void addFriendship(int a, int b) {
    // Add friendship (bidirectional)
    friends[a].push_back(b);
    friends[b].push_back(a);
}

In the above code, the addFriendship function adds a friendship relationship between two students.

3. Counting Friends

To count the number of friends of a specific student, we implement a function that returns the size of that student’s adjacency list. Below is an example implementation: 


int countFriends(int student) {
    return friends[student].size();
}

This code returns the size of the list of friends for a specific student from the adjacency list.

4. Checking Friendship Relationships

We also need a function to check whether two students are friends. This function searches through the adjacency list to see if the two students are in the same list of friends. Below is an example implementation: 


bool areFriends(int a, int b) {
    // Get A's list of friends
    for (int friend_id : friends[a]) {
        if (friend_id == b) {
            return true; // Friendship exists
        }
    }
    return false; // Friendship does not exist
}

The above function checks if student A has student B in their list of friends.

Complete Code

Now, I will write the complete code incorporating all the explanations given so far: 


#include 
#include 
#include 

using namespace std;

unordered_map > friends;

void addFriendship(int a, int b) {
    friends[a].push_back(b);
    friends[b].push_back(a);
}

int countFriends(int student) {
    return friends[student].size();
}

bool areFriends(int a, int b) {
    for (int friend_id : friends[a]) {
        if (friend_id == b) {
            return true;
        }
    }
    return false;
}

int main() {
    int N, M;
    cout << "Enter the number of students (N) and the number of friendship relations (M): ";
    cin >> N >> M;

    cout << "Enter friendship relations (e.g., A B): " << endl;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        addFriendship(a, b);
    }

    int query;
    cout << "Enter the number of the student to check the number of friends: ";
    cin >> query;
    cout << "Student " << query << " has " << countFriends(query) << " friends." << endl;

    int a, b;
    cout << "Enter the numbers of the two students to check their friendship relationship: ";
    cin >> a >> b;
    if (areFriends(a, b)) {
        cout << "Student " << a << " and student " << b << " are friends." << endl;
    } else {
        cout << "Student " << a << " and student " << b << " are not friends." << endl;
    }

    return 0;
}

Conclusion

In this tutorial, we closely examined the process of solving an algorithm problem that identifies friendship relationships using the C++ language. We learned how to model friendship relationships using important concepts from graph theory and data structures, and how to solve the problem through this modeling. Skills in solving such algorithmic problems are crucial for coding tests for employment, so I encourage you to strengthen your abilities through a variety of problems.