Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

For many years, the Genetic Evolution Laboratory (GEL) has been studying the evolution of various genetic diseases, by collecting, for each disease, data from a large population, over several generations. For each person, it is known whether the gene is dominant, recessive, or non-existent. Based on this data, scientists formulate an hypothesis on how the disease is transmitted from parents to children. However, it is tedious to check by hand if the data matches the hypothesis, so GEL asked you to automate this task for them.

The idea is simple: the program will, given the parent-child relationships and a fixed hypothesis, calculate for all people whether they have the gene or not, and in the former case whether it is dominant or not. This result is written to a text file, which will later be compared (using a standard file differencing tool) with the data that GEL collected. If there are no differences, the hypothesis is valid. Any mismatch will give clues to GEL's scientists on how they should improve the hypothesis.

Given a set of parent-child relationships, and the status of the gene for all those people whose parents are not in the data set, compute the status of the gene for all people in the data set, according to the following hypothesis:

• the child has the gene if, and only if, both parents have it or it is dominant in one of the parents; and
• the child's gene is dominant if, and only if, the gene is dominant in both parents or dominant in one and recessive in the other parent.

Input

The first line contains an integer N (1 <= N <= 3100), which is the number of lines of the data set.

Each of the following N lines contains a pair of non-empty strings, separated by a space. All strings are at most 20 characters long, and no string contains a blank (tab or space).

The first string is the name of a person. The second string is either

1. "non-existent", "recessive", or "dominant"; or
2. the name of another person (the child).

The first case is to indicate the status of the gene for a person whose parents are not part of the data set. The second case is to indicate that the first person is a parent of the second one.

All people have distinct names and none is "non-existent", "recessive", or "dominant".

For each person, either both or none of the parents are part of the data set.

Output

The output consists of one line per person occurring in the data set.

Each line has two strings, separated by a space. The first string is the name of the person, and the second string indicates the status of the gene, in the same way as in the input.

The output must be ordered alphabetically by name.

Sample Input

7
John dominant
Mary recessive
John Susan
Mary Susan
Peter non-existent
Susan Marta
Peter Marta

Sample Output

John dominant
Marta recessive
Mary recessive
Peter non-existent
Susan dominant

---

Concurso de Programa��o da Universidade do Porto'2004
CPN'2004: Segundo Concurso de Programa��o da Nova
Mar�o de 2004
Departamento de Inform�tica
Faculdade de Ci�ncias e Tecnologia
Universidade Nova de Lisboa

---

兩個人有這段基因或者其中一個人是顯性 <-> 孩子一定有這段基因。
兩個顯性 或 一顯一隱 <-> 孩子一定是顯性

題目就是要考驗推論的能力，保證一定能推出所有人。
還好測資不強！不然我用遞迴判定就會跑很久。

從父母推到孩子不難，但要考慮從孩子推到父母。

孩子是顯性 -> 當知道一個人是隱性時，另一個必然是顯性
孩子是隱性 -> 當知道一個人是沒基因時，另一個人必然是顯性
孩子沒有基因時 -> 當知道一個人是隱性食，另一個人必然是沒有基因。


#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <queue>
using namespace std;
struct E {
    int gene;
    string child;
    E() {
        gene = -1;
        child = "";
    }
};
map<string, E> R;
map<string, vector<string> > g;
int dfs(string name) {
    if(g[name].size() == 0) return R[name].gene;
    //cout << name << "---------"<< endl;
    E &val = R[name];
    if(val.gene < 0) {
        int g1 = dfs(g[name][0]);
        int g2 = dfs(g[name][1]);
        if(g1 >= 0 && g2 >= 0) {
            if((g1 > 0 && g2 > 0) || (g1 == 1 || g2 == 1)) {
                if(g1 == 1 && g2 == 1)
                    val.gene = 1;
                else if(g1 == 1 && g2 == 2)
                    val.gene = 1;
                else if(g1 == 2 && g2 == 1)
                    val.gene = 1;
                else
                    val.gene = 2;
            } else {
                val.gene = 0;
            }
        }
    } else {
        int g1 = dfs(g[name][0]);
        int g2 = dfs(g[name][0]);
        if(val.gene == 0) {
            if(g1 < 0 && g2 == 2) {
                R[g[name][0]].gene = 0;
                dfs(g[name][0]);
            }
            if(g2 < 0 && g1 == 2) {
                R[g[name][1]].gene = 0;
                dfs(g[name][1]);
            }
        }
        if(val.gene == 1) {
            if(g1 < 0 && g2 == 2) {
                R[g[name][0]].gene = 1;
                dfs(g[name][0]);
            }
            if(g2 < 0 && g1 == 2) {
                R[g[name][1]].gene = 1;
                dfs(g[name][1]);
            }
        }
        if(val.gene == 2) {
            if(g1 < 0 && g2 == 1) {
                R[g[name][0]].gene = 0;
                dfs(g[name][0]);
            }
            if(g1 < 0 && g2 == 2) {
                R[g[name][0]].gene = 2;
                dfs(g[name][0]);
            }
            if(g2 < 0 && g1 == 1) {
                R[g[name][1]].gene = 0;
                dfs(g[name][1]);
            }
            if(g2 < 0 && g1 == 2) {
                R[g[name][1]].gene = 2;
                dfs(g[name][1]);
            }
        }
    }
    return val.gene;
}
int main() {
    int n;
    while(scanf("%d", &n) == 1) {
        string s1, s2;
        R.clear();
        g.clear();
        E foo;
        while(n--) {
            cin >> s1 >> s2;
            if(s2 == "dominant")
                R[s1].gene = 1;
            else if(s2 == "recessive")
                R[s1].gene = 2;
            else if(s2 == "non-existent")
                R[s1].gene = 0;
            else {
                R[s1].child = s2;
                g[s2].push_back(s1);
                if(R.find(s2) == R.end())
                    R[s2] = foo;
            }
        }
        for(map<string, E>::iterator it = R.begin();
            it != R.end(); it++) {
            //cout << it->first <<" "<< it->second.child << "eee" << endl;
            if((it->second).child == "")
                dfs(it->first);
        }
        for(map<string, E>::iterator it = R.begin();
            it != R.end(); it++) {
            cout << it->first << " ";
            int val = it->second.gene;
            if(val == 0)
                puts("non-existent");
            else if(val == 1)
                puts("dominant");
            else if(val == 2)
                puts("recessive");
            else
                while(1);
            //cout << it->first << " " << it->second.gene << endl;
        }
    }
    return 0;
}