hdu 3172 Virtual Friends（并查集，字典树）

题意：人与人交友构成关系网，两个人交友，相当于两个朋友圈的合并，问每个出两人，他们目前所在的关系网中的人数。

分析：用并查集，其实就是求每个集合当前的人数。对于人名的处理用到了字典树。

注意：1、题目给出的n是指n对关系，上限有2*n个人。

　　 2、题目很没有意思的既说了有多组数据，又要求输入组数。实际上还是多组数据。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int MAXN=;

 struct Node{

     int c;

     Node *child[];

     Node(){

         c=;

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

             child[i]=NULL;

     }

  }*root;

 int cnt;

 int p[MAXN],num[MAXN];

 char str1[],str2[];

 void init(int n)

 {

     root=new Node();//

     cnt=;

     for(int i=;i<n;i++)

     {

         p[i]=i;

         num[i]=;

     }

 }

 int ID(char str[])

 {

     Node *p=root;

     int len=strlen(str);

     for(int i=,k;i<len;i++,p=p->child[k])

     {

         if(str[i]>='a'&&str[i]<='z')

             k=str[i]-'a';

         else

             k=str[i]-'A'+;

         if(p->child[k]==NULL)

             p->child[k]=new Node();

     }

     if(p->c)

         return p->c;

     return p->c=++cnt;//

 }

 int find(int x)

 {

     return p[x]==x?x:p[x]=find(p[x]);

 }

 int main()

 {

     int T,n;

      while(~scanf("%d",&T))

         {

             while(T--)

             {

                 scanf("%d",&n);

                 init(n*);//

                 for(int i=;i<n;i++)

                 {

                     scanf("%s%s",str1,str2);

                    int u=ID(str1);

                     int v=ID(str2);

                     int fu=find(u);

                     int fv=find(v);

                     if(fu==fv)

                         printf("%d\n",num[fu]);

                     else {

                         p[fv]=fu;

                         num[fu]+=num[fv];

                         printf("%d\n",num[fu]);

                     }

                 }

             }

     }

     return ;

 }

巴特西

hdu 3172 Virtual Friends（并查集，字典树）

最新文章

热门文章