[原创]codeforces766D Mahmoud and a Dictionary [并查集]【数据结构】

2017-02-08 23:55:44 Tabris_ 阅读数：552

博客爬取于2020-06-14 22:41:46
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54934767

题目连接：http://codeforces.com/contest/766/problem/D

----------------------------------------------------------------------------------------.
D. Mahmoud and a Dictionary
time limit per test4 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Mahmoud wants to write a new dictionary that contains n words and relations between them. There are two types of relations: synonymy (i. e. the two words mean the same) and antonymy (i. e. the two words mean the opposite). From time to time he discovers a new relation between two words.

He know that if two words have a relation between them, then each of them has relations with the words that has relations with the other. For example, if like means love and love is the opposite of hate, then like is also the opposite of hate. One more example: if love is the opposite of hate and hate is the opposite of like, then love means like, and so on.

Sometimes Mahmoud discovers a wrong relation. A wrong relation is a relation that makes two words equal and opposite at the same time. For example if he knows that love means like and like is the opposite of hate, and then he figures out that hate means like, the last relation is absolutely wrong because it makes hate and like opposite and have the same meaning at the same time.

After Mahmoud figured out many relations, he was worried that some of them were wrong so that they will make other relations also wrong, so he decided to tell every relation he figured out to his coder friend Ehab and for every relation he wanted to know is it correct or wrong, basing on the previously discovered relations. If it is wrong he ignores it, and doesn’t check with following relations.

After adding all relations, Mahmoud asked Ehab about relations between some words based on the information he had given to him. Ehab is busy making a Codeforces round so he asked you for help.

Input
The first line of input contains three integers n, m and q (2 ≤ n ≤ 105, 1 ≤ m, q ≤ 105) where n is the number of words in the dictionary, m is the number of relations Mahmoud figured out and q is the number of questions Mahmoud asked after telling all relations.

The second line contains n distinct words a1, a2, …, an consisting of small English letters with length not exceeding 20, which are the words in the dictionary.

Then m lines follow, each of them contains an integer t (1 ≤ t ≤ 2) followed by two different words xi and yi which has appeared in the dictionary words. If t = 1, that means xi has a synonymy relation with yi, otherwise xi has an antonymy relation with yi.

Then q lines follow, each of them contains two different words which has appeared in the dictionary. That are the pairs of words Mahmoud wants to know the relation between basing on the relations he had discovered.

All words in input contain only lowercase English letters and their lengths don’t exceed 20 characters. In all relations and in all questions the two words are different.

Output
First, print m lines, one per each relation. If some relation is wrong (makes two words opposite and have the same meaning at the same time) you should print “NO” (without quotes) and ignore it, otherwise print “YES” (without quotes).

After that print q lines, one per each question. If the two words have the same meaning, output 1. If they are opposites, output 2. If there is no relation between them, output 3.

See the samples for better understanding.

Examples
input
3 3 4
hate love like
1 love like
2 love hate
1 hate like
love like
love hate
like hate
hate like
output
YES
YES
NO
1
2
2
2
input
8 6 5
hi welcome hello ihateyou goaway dog cat rat
1 hi welcome
1 ihateyou goaway
2 hello ihateyou
2 hi goaway
2 hi hello
1 hi hello
dog cat
dog hi
hi hello
ihateyou goaway
welcome ihateyou
output
YES
YES
YES
YES
NO
YES
3
3
1
1
2

----------------------------------------------------------------------------------------.
题目大意:
就是有n个单词,有m个关系,q个查询,
关系是两个单词是同义词还是反义词,对于当前的这条关系如果与前述关系不符则忽略,
查询是两个单词之间的关系是同义词还是反义词还是未知.

解题思路:
很好想到并查集来维护同义词,然后用另一个数组怎样的表示两堆之间的反义词关系,

~~最开始是想对每堆进行染色,两个堆中一个染成+n,另一个染成-n,加和为零表示敌对关系,然后可以在维护一个并查集或者怎样 ,但是最后GG了~~

看了题解发现用另一个数组来维护本堆的反义词的堆是哪一个，真是奥妙重重。666

这样的话这个题目就简单清晰多了，直接维护就行了。

注意对于m条关系的判定时的细节就好了，详见代码。

借(chao)鉴(xi)这里<–戳戳戳

附本题代码
----------------------------------------------------------------------------------------.

int n,m,q,op;
string str,str1,str2;
map<string,int>mmp;
int pre[N],opp[N];

int findi(int x){
    int r = x;
    while(r != pre[r]) r=pre[r];

    int i=x,j;
    while(i!=j){
        j=pre[i];
        pre[i]=r;
        i=j;
    }

    return r;
}

void init(){
    mmp.clear();
    Rep(i,0,n) pre[i]=i,opp[i]=0;
}

int main(){

    while(cin>>n>>m>>q){
        init();

        Rep(i,1,n) cin>>str,mmp[str]=i;

        Rep(i,1,m){
            cin>>op>>str1>>str2;
            int x = mmp[str1],y = mmp[str2];
            int u = findi(x),v = findi(y);
            int uu= findi(opp[u]),vv= findi(opp[v]);
            if(op==1){
                if(uu!=v){
                    puts("YES");
                    pre[u]=v;
                    if(uu&&vv) pre[uu]=vv;
                    if(!vv)  opp[v]=uu;
                }
                else puts("NO");
            }
            else {
                if(u!=v) {
                    puts("YES");
                    if(uu) pre[v]=uu;
                    else   opp[u]=v;
                    if(vv) pre[u]=vv;
                    else   opp[v]=u;
                }
                else puts("NO");

            }
        }

        Rep(i,1,q){
            cin>>str1>>str2;
            int x = mmp[str1],y = mmp[str2];
            int u = findi(x),v = findi(y);
            int uu= findi(opp[u]),vv= findi(opp[v]);
            if (u==v) puts("1");
            else  {
                if (uu==v||vv==u) puts("2");
                else puts("3");
            }
        }

    }
    return 0;
}