Wenwen's ancestral home is a large family, and every time he returns home for the New Year, she always has trouble understanding the generational relationships, often treating elders as peers and speaking without regard to seniority. So her dad took out the family tree and reviewed the generational relationships between family members with Wenwen.
Now, take out the names of two people from this family tree, and compare their generational relationships.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line of input contains an integer N (1 ≤ N ≤ 100), representing the number of parent-child relationships in the family tree. Next, there are N lines, each containing two names a and b, indicating that a is the child of b. Finally, there is one query line containing two names p and q, representing the names for which we want to determine the relationship. It is guaranteed that each person in the family tree can be traced back to a common ancestor. | Output an integer: If p and q are of the same generation, output 0. If p is an ancestor of q, output a positive integer representing how many generations above q and p is. If p is a descendant of q, output a negative integer representing how many generations below q and p is. |
| 3 Jacob Isaac Isaac Abraham Ishmael Abraham Jacob Ishmael | -1 |
| 3 A ABC B ABC C ABC A C | 0 |
| 4 me dad dad grand-dad son me grand-son son grand-dad grand-son | 4 |
Thought Process
This problem can be modeled using a tree-like structure. You can create a struct to store each person's name, ancestors, and descendants. Then, you can use a map with the names as keys to store these structs. Finally, you can use BFS (Breadth-First Search) to traverse upwards and downwards from the given names. It's important to keep track of whether a name has been visited before using another map to avoid redundant computations.
Sample Code－ZeroJudge K862: Comparing Seniority
#include <iostream>
#include <map>
#include <vector>
using namespace std;
struct node
{
vector<node*>up;
vector<node*>down;
string name;
int val = 0;
};
map<string, node*>MAP;
map<string, int>walk;
string start, target;
int ans;
void BFS(vector<string>start)
{
if (start.size() == 0) return;
vector<string>newStart;
for (int i = 0; i<start.size(); i++)
{
string name = start[i];
walk[name] = 1;
if (name == target)
{
ans = MAP[name]->val;
return;
}
if (MAP[name]->up.size() != 0)
{
for (int j = 0; j<MAP[name]->up.size(); j++)
{
string fn = MAP[name]->up[j]->name;
if (walk[fn] == 0) {
MAP[fn]->val = MAP[name]->val - 1;
newStart.push_back(fn);
}
}
}
if (MAP[name]->down.size() != 0)
{
for (int j = 0; j<MAP[name]->down.size(); j++)
{
string fn = MAP[name]->down[j]->name;
if (walk[fn] == 0) {
MAP[fn]->val = MAP[name]->val + 1;
newStart.push_back(fn);
}
}
}
}
BFS(newStart);
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for (int i = 0; i<N; i++)
{
string a, b;
cin >> a >> b;
if (MAP[a] == nullptr)
{
node* tmp = new node();
tmp->name = a;
MAP[a] = tmp;
}
if (MAP[b] == nullptr)
{
node* tmp = new node();
tmp->name = b;
MAP[b] = tmp;
}
MAP[a]->up.push_back(MAP[b]);
MAP[b]->down.push_back(MAP[a]);
}
cin >> start >> target;
vector<string>v;
v.push_back(start);
BFS(v);
cout << ans << "\n";
}
//ZeroJudge K862
//Dr. SeanXD