URAL 1242. Werewolf

Author: 2015-08-21

ACM

, ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1242

1242. Werewolf

Time limit: 1.0 second
Memory limit: 64 MB
Knife. Moonlit night. Rotten stump with a short black-handled knife in it. Those who know will understand. Disaster in the village. Werewolf.
There are no so many residents in the village. Many of them are each other’s relatives. Only this may help to find the werewolf. The werewolf is merciless, but his descendants never become his victims. The werewolf can drown the village in blood, but he never kills his ancestors.
It is known about all the villagers who is the child of whom. Also, the sad list of the werewolf’s victims is known. Your program should help to determine the suspects. It would be a hard task, if a very special condition would not hold. Namely, citizens of the village are not used to leave it. If some ancestor of some citizen lives in the village, then also his immediate ancestor does. It means, that, for example, if the father of the mother of some citizen still lives in the village, than also his mother still lives.

Input

The first line contains an integer N, 1 < N ≤ 1000, which is the number of the villagers. The villagers are assigned numbers from 1 to N. Further is the description of the relation “child-parent”: a sequence of lines, each of which contains two numbers separated with a space; the first number in each line is the number of a child and the second number is the number of the child’s parent. The data is correct: for each of the residents there are no more than two parents, and there are no cycles. The list is followed by the word “BLOOD” written with capital letters in a separate line. After this word there is the list of the werewolf’s victims, one number in each line.

Output

The output should contain the numbers of the residents who may be the werewolf. The numbers must be in the ascending order and separated with a space. If there are no suspects, the output should contain the only number 0.

Samples

input output 
8
1 3
3 6
4 5
6 2
4 6
8 1
BLOOD
3
8

4 5 7

6
1 2
3 2
1 4
3 4
2 6
5 2
5 4
BLOOD
2
5

0
Problem Author: Leonid Volkov
Problem Source: Ural State University Personal Programming Contest, March 1, 2003

2. 思路

村子里潜伏着狼人（人形态），狼人不会伤害自己的后代和祖先，给出一系列村民和他们之间的关系，并给出受害者名单，求哪些人可能是狼人。

题目中用的是“the werewolf”，狼人只有一只，不需要考虑两支家族的两只狼人互杀对家的情况。由于“the werewolf”不会伤害自己的后代和祖先，则受害者的后代和祖先一定是人类。对每个受害者，DFS其后代和祖先，标记为人类，搜索完所有受害者之后，没被标记为人类的即为狼人嫌疑犯。

3. 代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define MAX_N 1001
#define LINE_BUF_LEN 10

typedef struct RelationRecord{
    short id;
    struct RelationRecord *next;
} Relation;

void solveE3e_Werewolf();
int inputRelation(Relation *descendants[], Relation *ancestors[]);
void addRelation(Relation *relation[], int id, int newRelation);
void dfs(Relation *relation[], int id);

int main() {
    // freopen("test_2.txt", "r", stdin);
    solveE3e_Werewolf();
}

Relation *descendants[MAX_N], *ancestors[MAX_N];
bool isHuman[MAX_N];
void solveE3e_Werewolf() {
    int n = inputRelation(descendants, ancestors);

    char line[LINE_BUF_LEN];
    int victim;
    while (scanf("%[^\n]", line) != EOF) {
        getchar();
        sscanf(line, "%d", &victim);
        dfs(descendants, victim);
        dfs(ancestors, victim);
    }

    bool found = false;
    for (int i = 1; i <= n; ++i) {
        if (!isHuman[i]) {
            printf("%d ", i);
            found = true;
        }
    }

    if (!found)
        printf("0\n");
    else
        printf("\n");
}

int inputRelation(Relation *descendants[], Relation *ancestors[]) {
    int n;
    scanf("%d", &n);
    getchar();

    char line[LINE_BUF_LEN];
    scanf("%[^\n]", line);
    getchar();
    int child, parent;
    while (line[0] != 'B') {
        sscanf(line, "%d %d", &child, &parent);

        addRelation(descendants, parent, child);
        addRelation(ancestors, child, parent);

        scanf("%[^\n]", line);
        getchar();
    }

    return n;
}

void addRelation(Relation *relation[], int id, int newRelation) {
    Relation *r = new Relation();
    r->id = newRelation;
    r->next = relation[id];
    relation[id] = r;
}

void dfs(Relation *relation[], int id) {
    isHuman[id] = true;

    Relation *r = relation[id];
    while (r != NULL) {
        dfs(relation, r->id);
        r = r->next;
    }
}