Editorial for Study Group

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: oree

In this problem, we want to track each of the friends in the order in which they start studying, cutting off the traversal once we reach 7 jumps, and count the number of friends we have visited. Although some might not have seen it before, this is a classic application of a graph breadth-first search (BFS).

To do BFS, we first build up a so-called adjacency list from the input. This is a map from strings to vectors of strings, which tells us who each person is friends with. Then, we need a set to track which people we've seen so far, and a queue to do the traversal. Since friendships are both ways, we don't want to be stuck visiting the same people in an infinite loop, and since someone might have multiple friends, we want some way to track them all in the right order to visit. In the queue, we can also store an integer representing the day, which we increment on each hop. That way, if we ever see the number 7, we know we've reached the end. To see the amount of people we have visited, we could use a counter, but we can also just use the size of the seen set.

This solution runs with O(n) for both time and space, as we will only visit each person up to once, and use the queue to store the friends to visit.

C++ solution:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;

    unordered_map<string, vector<string>> adj;
    string you = "";
    while (n--) {
        string name, closeFriend;
        int degree;
        cin >> name >> degree;
        if (you == "") you = name;
        while (degree--) {
            cin >> closeFriend;
            adj[name].push_back(closeFriend);
        }
    }

    unordered_set<string> seen;
    queue<pair<int, string>> q;
    q.push({ 1, you });

    while (!q.empty()) {
        auto [day, name] = q.front();
        q.pop();
        if (day > 7) break;
        seen.insert(name);
        for (auto& closeFriend : adj[name]) {
            if (!seen.contains(closeFriend)) {
                q.push({ day + 1, closeFriend });
            }
        }
    }
    cout << seen.size() << endl;
}

Python solution:

from collections import deque

n = int(input())

adj = {}

you = None
for _ in range(n):
    name, _ = input().split()
    if you is None:
        you = name
    adj[name] = input().split()


q = deque()
q.append((1, you))
seen = set()

while q:
    day, name = q.popleft()
    if day > 7:
        break
    seen.add(name)

    for friend in adj[name]:
        if friend not in seen:
            q.append((day + 1, friend))

print(len(seen))

Comments

There are no comments at the moment.