• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            C小加

            厚德 博學(xué) 求真 至善 The bright moon and breeze
            posts - 145, comments - 195, trackbacks - 0, articles - 0
              C++博客 :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理
            NYOJ地址:http://acm.nyist.net/JudgeOnline/problem.php?pid=431
            并查集
            訓(xùn)練賽的時(shí)候強(qiáng)出了這個(gè)題,沒(méi)有過(guò),月賽的時(shí)候獲哥又拿上來(lái)了,結(jié)果還是沒(méi)過(guò)。后來(lái)聽(tīng)獲哥講明白了,F(xiàn)ind函數(shù)沒(méi)有處理好。最后總結(jié)了一下,并查集的本質(zhì)還是沒(méi)有理解透徹,處理節(jié)點(diǎn)與根節(jié)點(diǎn)的關(guān)系時(shí)總是很混亂。 

            題意:一共有n個(gè)龍珠和n個(gè)城市,第i顆龍珠在第i座城市。下面有兩種操作:
            T a b 將a龍珠所在的城市的所有龍珠移動(dòng)到第b個(gè)龍珠所在的城市
            Q a 詢問(wèn)a龍珠所在的城市,這座城市有多少顆龍珠,a龍珠被移動(dòng)了多少次

            思路:看懂題意后就知道用并查集了。詢問(wèn)的前兩個(gè)問(wèn)題都很好解決,有點(diǎn)難度的是第三個(gè)問(wèn)題,龍珠被移動(dòng)的次數(shù)。我用count數(shù)組統(tǒng)計(jì)每顆龍珠移動(dòng)的次數(shù),路徑壓縮后,每顆龍珠的父親就是它所在的城市,如果這顆龍珠所在的城市所有的龍珠被移走的話,這座城市變成一座空城市,所以不會(huì)有龍珠再被移動(dòng)到這座城市,就是說(shuō)一座城市只能轉(zhuǎn)移一次,假設(shè)a所在的城市的所有龍珠移動(dòng)到了b,合并的時(shí)候統(tǒng)計(jì)這座城市移動(dòng)的次數(shù),那么統(tǒng)計(jì)龍珠的時(shí)候,只要統(tǒng)計(jì)它的父親它的祖父一直到它的老祖,每個(gè)長(zhǎng)輩的count和就是這顆龍珠的移動(dòng)次數(shù)。所以在Union的時(shí)候讓它父親的count++,F(xiàn)ind的時(shí)候讓它遍歷到根節(jié)點(diǎn)每次都加上一個(gè)長(zhǎng)輩的count。寫(xiě)完后會(huì)感覺(jué)到,就是一個(gè)裸體的并查集。
            #include <iostream>
            #include 
            <cstdio>
            #include 
            <cstring>
            using namespace std;

            const int MAXN=10003;
            int father[MAXN],sum[MAXN],count[MAXN];
            void Init(int n)
            {
                
            for(int i=0;i<=n;i++)
                {
                    father[i]
            =i;
                    sum[i]
            =1;
                    count[i]
            =0;
                }
            }

            int Find(int x)
            {
                
            int temp;
                
            if(x==father[x]) return x;
                
            else
                {
                    temp
            =father[x];
                    father[x]
            =Find(father[x]);
                    count[x]
            +=count[temp];
                }
                
            return father[x];
            }

            void Union(int a,int b)
            {
                
            int x=Find(a);
                
            int y=Find(b);
                
            if(x==y) return;
                
            else
                {
                    father[x]
            =y;
                    count[x]
            ++;
                    sum[y]
            +=sum[x];
                    sum[x]
            =0;
                }
            }

            int main()
            {
                
            //freopen("input","r",stdin);
                
            //freopen("out","w",stdout);
                int t,cnt=1;
                scanf(
            "%d",&t);
                
            while(t--)
                {
                    
            int m,n;
                    scanf(
            "%d%d",&m,&n);
                    printf(
            "Case %d:\n",cnt++);
                    Init(m);
                    
            while(n--)
                    {
                        
            char s1;
                        getchar();
                        scanf(
            "%c",&s1);


                        
            if(s1=='T')
                        {
                            
            int a,b;
                            scanf(
            "%d%d",&a,&b);
                            Union(a,b);

                        }
                        
            else
                        {
                            
            int p;
                            scanf(
            "%d",&p);
                            
            int temp=Find(p);
                            printf(
            "%d %d %d\n",temp,sum[temp],count[p]);
                        }
                    }

                }


                
            return 0;
            }
                    
            中文字幕人妻色偷偷久久| AV无码久久久久不卡网站下载| 青青草原综合久久大伊人精品| 国产精品99久久99久久久| 久久精品国产一区| 婷婷久久综合九色综合绿巨人| 亚洲中文字幕无码久久综合网| 精品综合久久久久久97超人| 久久免费香蕉视频| 国产精品一区二区久久| 久久久高清免费视频| 久久―日本道色综合久久| 精品多毛少妇人妻AV免费久久| 国产高潮国产高潮久久久| 久久这里有精品| 久久久久免费精品国产| 伊人久久大香线蕉综合Av| 久久精品国产一区二区 | 亚洲精品国产美女久久久| 国产精品久久久久乳精品爆| 无码国产69精品久久久久网站| 伊人热热久久原色播放www| 93精91精品国产综合久久香蕉| 久久人人爽人人爽人人AV东京热| 久久久久18| 久久成人国产精品一区二区| 99久久中文字幕| 久久se精品一区二区| 777米奇久久最新地址| 久久国产精品77777| 亚洲va中文字幕无码久久| 国产色综合久久无码有码| 久久91精品国产91久| 久久只有这里有精品4| 模特私拍国产精品久久| 亚洲人成电影网站久久| 亚洲午夜精品久久久久久浪潮 | 偷偷做久久久久网站| 久久国产美女免费观看精品| 国产成人精品久久一区二区三区av| www久久久天天com|