224. Supervisors and Subordinates

I'm a slow walker, but I never walk backwards.

Task Description

寫一個程式決定兩個員工的關係。程式的主程式和初始化的函數已寫好,因此你要做的是實作三個輔助函數和判斷關係的函數。三個輔助函數分別是:以名字找員工、以員工編號找員工、找一名員工最頂層的的老闆。

員工的資料我們定義如下:每一個員工有一個唯一的員工號碼 id,姓 last_name,名 first_name,及直屬上司的員工號碼 boss_id。每個員工只有一個直屬上司,而且可以是自己。在這份作業中,我們以一個結構來定義員工資料。

employee.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#ifndef _EMPLOYEE_H
#define _EMPLOYEE_H
 
struct employee{
    int id;
    char first_name[32];
    char last_name[32];
    int boss_id;
};
typedef struct employee Employee;
 
void init_storage(Employee **storage, int n);
void free_storage(Employee **storage);
Employee* find_employee_by_id( Employee *set, int n, int id );
Employee* find_employee_by_name( Employee *set, int n, const char *first_name, const char *last_name );
Employee* find_root_boss( Employee *set, int n, Employee *employee );
int check_relationship(Employee *set, int n, Employee *A, Employee *B);
 
#endif

初始化和結束的兩個函數實作請見以下。

employee.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "employee.h"
 
void init_storage(Employee **storage, int n)
{
    // allocate memory space to store employee data
    // no need to understand this function now.
 
    (*storage) = (Employee *)malloc(sizeof(Employee) * n);
}
 
void free_storage(Employee **storage)
{
    free(*storage);
    *storage = 0;
}

主程式流程則請見以下。

main.c

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
#include <stdio.h>
#include "employee.h"
 
int main()
{
    int n, m;
    int i;
    Employee *set = NULL;
 
    scanf("%d", &n);
    init_storage(&set, n);
    for ( i = 0 ; i < n ; i++ )
        scanf("%d %s %s %d", &(set[i].id), set[i].first_name, set[i].last_name, &(set[i].boss_id));
    char first_name_A[32], first_name_B[32];
    char last_name_A[32], last_name_B[32];
    Employee *A, *B;
    int type;
 
    scanf("%d", &m);
    for ( i = 0 ; i < m ; i++ )
    {
        scanf("%s %s", first_name_A, last_name_A); 
        A = find_employee_by_name(set, n, first_name_A, last_name_A);
 
        scanf("%s %s", first_name_B, last_name_B); 
        B = find_employee_by_name(set, n, first_name_B, last_name_B);
 
        type = check_relationship(set, n, A, B);
        switch(type){
            case 1:
                printf("subordinate\n"); break;
            case 2:
                printf("supervisor\n"); break;
            case 3:
                printf("colleague\n"); break;
            default:
                printf("unrelated\n"); break;
        }
    }
    free_storage(&set);
    return 0;
}

兩個員工 A 和 B 的關係定義如下:

  • 如果 A 可藉由一連串的「直屬上司」關係連結到 B,則稱 A 是 B 的部屬 (subordinate) 。
  • 如果 B 可藉由一連串的「直屬上司」關係連結到 A,則稱 A 是 B 的長官 (supervisor) 。
  • 如果 A 與 B 並非部屬/長官關係,但存在另一個 C,且 A 與 B 皆為 C 的部屬,則 A 和 B 互為同事(colleague) 關係。
  • 如果以上皆非,則 A 與 B 為無關係 (unrelated)。

Input

輸入的第一行為 $n$,代表員工數目。以下 $n$ 行都為員工號碼、姓、名及直屬上司的員工號碼。接下來會有一個數字 $m$ 代表查詢次數,以下 $m$ 行為想查詢的兩個員工姓名。員工的姓名保證存在於輸入中,且代表兩個不同的員工。

Output

輸出有 $m$ 行,每一行為想查詢的兩個員工姓名之間的關係。關於輸入輸出的處理和分工,以及初始化函數的使用,請參閱主程式。

Limits

$0 \lt n \le 32 , \; 0 \lt m$

Sample input

6
100 John Smith 200
200 Adam Johnson 300
300 Jane Washington 300
400 Mary Miller 300
500 Eric Page 500
600 James Clark 500
4
John Smith Adam Johnson
Jane Washington Adam Johnson
Adam Johnson Mary Miller
Mary Miller James Clark

Sample output

subordinate
supervisor
colleague
unrelated

Discussion