C - 无间道之并查集 HihoCoder

输入

每个测试点（输入文件）有且仅有一组测试数据。

每组测试数据的第1行为一个整数N，表示黑叔叔总共进行的操作次数。

每组测试数据的第2~N+1行，每行分别描述黑叔叔的一次操作，其中第i+1行为一个整数op_i和两个由大小写字母组成的字符串Name1_i, Name2_i，其中op_i只可能为0或1，当op_i=0时，表示黑叔叔判定Name1_i和Name2_i是同一阵营的，当op_i=1时，表示黑叔叔希望知道Name1_i和Name2_i是否为同一阵营的。

对于100%的数据，满足N<=10^5, 且数据中所有涉及的人物中不存在两个名字相同的人（即姓名唯一的确定了一个人），对于所有的i，满足Name1_i和Name2_i是不同的两个人。

输出

对于每组测试数据，对于黑叔叔每次op_i=1的操作，输出一行，表示查询的结果：如果根据已知信息（即这次操作之前的所有op_i=0的操作），可以判定询问中的两个人是同一阵营的，则输出yes，否则输出no。

对于map，这类c++的东西一直都不太熟悉，之前AC这道题果断绕过了map,但是想想那样是不对的，所以又重新做了一遍。

#include<stdio.h>

#include<string.h>

int par[100000];

char c[100000][20];

int cnt=0;

int _find (int x)

{

    if(par[x]==x)

    {

        return x;

    }

    else{

        return par[x]=_find(par[x]);

    }

}

void unite (int x,int y)

{

    x=_find(x);

    y=_find(y);

    if(x!=y) par[x]=y;

}

int pp(char a[])

{   int i;

    for( i=0;i<=cnt;i++)

    {

       if(strcmp(c[i],a)==0)

             return par[i];

    }

    cnt++;

    strcpy(c[cnt],a);

    par[cnt]=cnt;

    return cnt;

}

int main()

{

   char a[20],b[20];

   int T,n,i;

    int oo1,oo2;

    scanf("%d",&T);

      for( i=0;i<T;i++)

       {

           memset(a,0,sizeof(a));

           memset(b,0,sizeof(b));

           scanf("%d",&n);

           scanf("%s",a);

             oo1=pp(a);

           scanf("%s",b);

             oo2=pp(b);

           if(n==0)

           {

            unite(oo1,oo2);

           }

           else{

            if(_find(oo1)==_find(oo2))

                printf("yes\n");

            else

                printf("no\n");

           }

       }

    return 0;

}

map:

#include<stdio.h>

#include<iostream>

#include<string.h>

using namespace std;

#include<map>

int par[20005];

void init()

{

    for(int i=0; i<=20000; i++)

    {

        par[i]=i;

    }

}

int find (int x)

{

    if(par[x]==x)

    {

        return x;

    }

    else

    {

        return par[x]=find(par[x]);

    }

}

void unite (int x,int y)

{

    x=find(x);

    y=find(y);

    if(x!=y) par[x]=y;

}

int main()

{

    init();

    int T;

    map<string,int > m;

    string ca,cb;

    int cnt = 0;

    int flag;

    scanf("%d",&T);

    while(T--)

    {

        cin >> flag >> ca >> cb;

        int ida;

        ida = m[ca];

        int idb;

        idb = m[cb];

        if( ida == 0 )

        {

            m[ca] = ++cnt;

            ida = m[ca];

        }

        if(idb == 0)

        {

            m[cb] = ++cnt;

            idb = m[cb];

        }

        if(flag == 0)

        {

            unite(ida,idb);

        }

        else

        {

            if(find(ida)==find(idb))

                cout<<"yes"<<endl;

            else cout<<"no"<<endl;

        }

    }

    return 0;

}

巴特西

C - 无间道之并查集 HihoCoder - 1066

最新文章

热门文章