hdu1856【栾宫涅吧】

栾宫涅吧关注：6贴子：216

3回复贴，共1页

hdu1856

并查集
TLE了N次，要注意数的构造，防止深度太大，搜起来费时。
第一次用STL写的，悲剧的TLE了
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
int main()
{
     vector< list<int> > u;
     vector< list<int> >::iterator it,ita,itb;
     list<int>::iterator itla,itlb;
     int n,a,b,max;
     bool uaf,ubf;

     while (scanf("%d",&n))
     {
           max=0;
           u.clear();
           while (n--)
           {
                 uaf=false;
                 ubf=false;
                 scanf("%d%d",&a,&b);
                 for (it=u.begin(); it!=u.end(); it++)
                 {
                     itla = find(it->begin(), it->end(), a);
                     itlb = find(it->begin(), it->end(), b);
                     if (itla!=it->end()) { ita=it; uaf=true; }
                     if (itlb!=it->end()) { itb=it; ubf=true; }
                     if (uaf && ubf) break;
                 }
/*                 cout<<"uaf="<<uaf<<"     ubf="<<ubf<<endl;*/
                 if (uaf && ubf)
                 {
                    ita->splice(ita->begin(), *itb);
                    itb=u.erase(itb);

送TA礼物

1楼2011-05-30 20:05回复

                 }
                 else if (uaf)
                 {
                      ita->push_back(b);
                 }
                 else if (ubf)
                 {
                      itb->push_back(a);
                 }
                 else
                 {
                     list<int> *temp;
                     temp=new(list<int>);
                     temp->push_back(a);
                     temp->push_back(b);
                     u.push_back(*temp);
                     delete(temp);
                 }
/*
                 for (it=u.begin(); it!=u.end(); it++)
                 {
                     for (itla=it->begin(); itla!=it->end(); itla++)
                         cout<<*itla<<"    ";
                     cout<<endl;
                 }

2楼2011-05-30 20:05

*/
           }
           for (it=u.begin(); it!=u.end(); it++)
               if (max < it->size()) max=it->size();
           cout<<max<<endl;
     }
     return 0;
}
后来用就用树写，还是TLE：
#include <stdio.h>
#define MAXN 10000002
int p[MAXN],num[MAXN];
int a,b,n,i,max;
void init()
{
     max=1;
     for (i=0;i<MAXN;i++)
     {
         p[i]=i;
         num[i]=1;
     }
}
int find(int x)
{
     int i=x;
     while (i!=p[i]) i=p[i];
     return i;
}
void unit(int a, int b)
{
     int pa=find(a);
     int pb=find(b);
     if (pa!=pb)
     {
         p[pb]=pa;
         num[pa]+=num[pb];
         if (max<num[pa]) max=num[pa];
     }
}
int main()
{
     while (scanf("%d",&n)!=EOF)
     {
         init();
         while(n--)
         {
             scanf("%d%d",&a,&b);
             unit(a,b);
         }
         //printf("%d\n",max);
         for (i=0;i<MAXN;i++)
             if (max<num[i]) max=num[i];
         printf("%d\n",max);
     }
     return 0;
}
再后来对构造父节点优化了下，终于AC了：
#include <stdio.h>
#define MAXN 10000002
int p[MAXN],num[MAXN];
int main()
{
     int a,b,n,i,max;
     while (scanf("%d",&n)!=EOF)
     {
         max=1;
         for (i=0;i<MAXN;i++)
         {
             p[i]=i;
             num[i]=1;

3楼2011-05-30 20:05

         }
         while(n--)
         {
             scanf("%d%d",&a,&b);
             while (a!=p[a]) a=p[a];
             while (b!=p[b]) b=p[b];
             if (a!=b)
                if (num[a]>=num[b])
                {
                   p[b]=a;
                   num[a]+=num[b];
                   if (max<num[a]) max=num[a];
                }
                else
                {
                    p[a]=b;
                    num[b]+=num[a];
                    if (max<num[b]) max=num[b];
                }
         }
         printf("%d\n",max);
     }
     return 0;
}

4楼2011-05-30 20:05

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

贴吧热议榜

3回复贴，共1页

<返回栾宫涅吧

发表回复

发贴请遵守贴吧协议及“七条底线”贴吧投诉

内容:

使用签名档查看全部

发表

保存至快速回贴

日	一	二	三	四	五	六

hdu1856

登录百度账号

扫二维码下载贴吧客户端