Find them, Catch them（并查集）

题意：有两个黑帮团伙，共n名团伙成员（不知道属于这两个黑帮中的哪一个）。现在警察有一些信息，每条信息包含2个人的编号，如果给出A a b,则输出a b的关系，即是否属于同一个黑帮；

如果给出D a b,则说明a b属于不同的黑帮。

思路：典型的并查集，只要两者的关系确定了，就将他们放入同一个集合内，而另外增加一个表示关系的数组link[]来表示该节点与其父亲的关系，0表示同一类，1表示不同团伙。初始时集合只有自己一个元素,link[] 初始为0。

第一次用c++的输入输出，TLE了。。改成C的就A了。

TLE 代码：

 #include <iostream>

 #include <string>

 using namespace std;

 const int N=;

 int f[N],link[N];

 int n,m;

 int find(int x)

 {

     int t = f[x];

     if (x!=f[x])

         f[x] = find(f[x]);

     link[x] = (link[x]==link[t] ?  : );

     return f[x];

 }

 void merge(int x,int y,int fu,int fv)

 {

     f[fu] = fv;

     link[fu] = (link[x]==link[y] ?  : );

 }

 void init()

 {

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

     {

         f[i] = i;

         link[i] = ;

     }

 }

 int main()

 {

     int T;

     cin>>T;

     while(T--)

     {

         cin>>n>>m;

         init();

         while(m--)

         {

             int u,v;

             char s;

             cin>>s>>u>>v;

             int fu = find(u);

             int fv = find(v);

             if (s=='A')

             {

                 if(fu!=fv)

                 {

                     cout<<"Not sure yet."<<endl;

                     continue;

                 }

                 if (link[u]==link[v])

                 {

                     cout<<"In the same gang."<<endl;

                     continue;

                 }

                 cout<<"In different gangs."<<endl;

                 continue;

             }

             if (s=='D')

             {

                 if (fu!=fv)

                     merge(u,v,fu,fv);

             }

         }

     }

     return ;

 }

AC代码：

 #include <stdio.h>

 const int N=;

 int f[N],link[N];

 int n,m;

 int find(int x)

 {

     int t = f[x];

     if (x!=f[x])

         f[x] = find(f[x]);

     link[x] = (link[x]==link[t] ?  : );

     return f[x];

 }

 void merge(int x,int y,int fu,int fv)

 {

     f[fu] = fv;

     link[fu] = (link[x]==link[y] ?  : );

 }

 void init()

 {

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

     {

         f[i] = i;

         link[i] = ;

     }

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d%*c",&n,&m);

         init();

         while(m--)

         {

             int u,v;

             char s;

             scanf("%c%d%d%*c",&s,&u,&v);

             int fu = find(u);

             int fv = find(v);

             if (s=='A')

             {

                 if(fu!=fv)

                 {

                     printf("Not sure yet.\n");

                     continue;

                 }

                 if (link[u]==link[v])

                 {

                     printf("In the same gang.\n");

                     continue;

                 }

                 printf("In different gangs.\n");

                 continue;

             }

             if (s=='D')

             {

                 if (fu!=fv)

                     merge(u,v,fu,fv);

             }

         }

     }

     return ;

 }

巴特西

Find them, Catch them（并查集）

最新文章

热门文章