ZeroJudge A584: Relative Relations

The social studies teacher in Xiao Ming's class asked the students to discuss how to distinguish and calculate the first, second, and third degrees of kinship in law, and report on it in the next class. Xiao Ming found a suggestion for calculating kinship on the Internet – drawing a tree diagram. In the diagram, each node represents a person's name, and the parent node stores the name of their father, while the child nodes store the names of their children. In the tree diagram, the number of links needed to connect two relatives is the degree of kinship between them. For example, in the diagram below, LIZ and her father BOB are only one link apart, so they are first-degree relatives, while LIZ and her grandfather PAM require two links, making them second-degree relatives. Additionally, LIZ needs to go through four links to connect with JIM, so they are fourth-degree relatives. Can you write a program to automatically determine the degree of kinship between two people?

ZeroJudge A584題目解說用圖

To simplify the problem, we made the following restrictions:

  1. We represent both parents by the name of the father, and both grandparents by the name of the grandfather.
  2. Each node will have a number of child nodes depending on the number of biological children associated with that node's name, but it will not exceed ten at most.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The input consists of N+2 lines (1 ≤ N ≤ 50). The first line contains only one value, N, indicating there are N records to build the tree structure. The 2nd to the N+1 lines each contain one record. In each record, the first English name is the name of a node, and the subsequent English names are the names of the child nodes of that node. Names are separated by spaces, and there is no order relationship between the records, but a tree structure can always be constructed. The last line of input contains the names of two different individuals for determining their degree of kinship (these names will appear in the input data), separated by a space. In the input data, all English names consist of three uppercase letters.Please output a number representing the degree of relationship between the two individuals.
3
PAM BOB TOM PAT
BOB LIZ ANN
PAT JIM
LIZ TOM		3
2
BOB LIZ ANN
PAM BOB TOM
LIZ ANN		2

Thought Process

Use a Map to store the relationships of each person, utilize StringStream to split strings, and employ BFS to find the starting point for each search for individuals.

Sample Code－ZeroJudge A584: Relative Relations

#include <iostream>
#include <sstream>
#include <map>
#include <vector>
using namespace std;

map<string, vector<string>>MAP;
map<string, int>walk;
int counts = 0;

void BFS(vector<string>start, string target)
{
    if (start.size() == 0) return;
    vector<string>newStart;
    for (int i = 0; i<start.size(); i++)
    {
        if (start[i] == target) return;
        vector<string>v = MAP[start[i]];
        walk[start[i]] = 1;
        for (int j = 0; j<v.size(); j++)
        {
            if (walk[v[j]] == 0) newStart.push_back(v[j]);
        }
    }
    counts++;
    BFS(newStart, target);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    string tmp;
    getline(cin, tmp);
    for (int i = 0; i<N; i++)
    {
        string str;
        getline(cin, str);
        stringstream ss;
        ss.clear();
        ss<<str;
        bool first = true;
        string start;
        while (true)
        {
            string s;
            ss>>s;
            if (ss.fail()) break;
            if (first)
            {
                start = s;
                first = false;
            }
            else
            {
                MAP[start].push_back(s);
                MAP[s].push_back(start);
            }
        }
    }
    string a, b;
    cin >> a >> b;
    vector<string>v;
    v.push_back(a);
    BFS(v, b);
    cout << counts << "\n";
}

//ZeroJudge A584
//Dr. SeanXD
Tags

Related Posts

Comments