Problem Solving►UVa

UVa 115 - Climbing Trees

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

中文網址

Solution

注意各層關係，0 級時是 parent(child)、1 級時 有 grand、再來才是 great …

用 node[N] 來存各個人的祖先，node[x] = x 的祖先 (最近的)
然後在比較兩人時，分別存下那兩人祖先一直往上的順序(直到源頭)，一邊比較是不是直系血親(在同一條上)，又或是 sibling(同個家長、0 級) or cousin。
Pair getRelation(int first,int second) 回傳兩人有關的祖先順位。

最後在依相差的順位來做輸出的格式。

直接看 code 可以比較好理解。

Code

UVa 115
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<utility>
#include<algorithm>
#define N 301
using namespace std;
typedef pair<int, int> Pair;

/*
node[x] = x 的祖先
注意 0 號為沒有祖先了
*/
int node[N] = {};
Pair getRelation(int first,int second)
{
    /*
    如果關係為 cousin:
    lev1,lev2 分別存共同祖先的各個順位

    如果某一方為另一方的 祖先:
    lev1 = 存他祖先的順位
    lev2 = -1
    反之則關係相反
    */

    int order1[N] = {}, order2[N];//[x] = x 的順位
    int lev1 = -1, lev2 = -1;
    int count = 1;//計算目前順位
    int next = node[first];

    while (next)
    {
        order1[next] = count++;
        next = node[next];
    }

    if (order1[second])//n 是 this 的 祖先
        lev1 = order1[second];
    else
    {
        next = node[second];
        count = 1;
        while (next)
        {
            if (order1[next])//n 和 this 為 cousin
            {
                lev1 = order1[next];
                lev2 = count;
                break;
            }
            else if (next == first)//this 是 n 的祖先
            {
                lev2 = count;
                break;
            }

            order2[next] = count++;
            next = node[next];
        }
    }

    return make_pair(lev1, lev2);
}
int main()
{
    string child, parent;
    map<string, int> Map;
    int mapId = 1;//0 是沒祖先

    while (cin >> child >> parent)
    {
        if (!strcmp(child.c_str(), "no.child"))
            break;

        if (!Map.count(child))
            Map[child] = mapId++;
        if (!Map.count(parent))
            Map[parent] = mapId++;
        
        node[Map[child]] = Map[parent];
    }

    string a, b;
    pair<int, int> relation;

    while (cin >> a >> b)
    {
        if (Map[a] == Map[b])//自己和自己沒關係
            puts("no relation");
        else
        {
            relation = getRelation(Map[a], Map[b]);
            int par1 = relation.first, par2 = relation.second;

            if (par1 != -1 && par2 != -1)
            {
                if (par1 == 1 && par2 == 1)//兄弟
                    puts("sibling");
                else//cousin
                {
                    int diff = abs(par1 - par2);
                    printf("%d cousin", min(par1, par2) - 1);
                    if (diff)
                        printf(" removed %d", diff);
                    putchar('\n');
                }
            }
            else if (par1 != -1)//a 是 b 的子孫
            {
                if (par1 > 1)
                {
                    for (int i = 1; i < par1 - 1; i++)
                        printf("great ");
                    puts("grand child");
                }
                else
                    puts("child");
            }
            else if (par2 != -1)//a 是 b 的祖先
            {
                if (par2 > 1)
                {
                    for (int i = 1; i < par2 - 1; i++)
                        printf("great ");
                    puts("grand parent");
                }
                else
                    puts("parent");
            }
            else//沒關係
                puts("no relation");
        }
    }

    return 0;
}