• <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>

            O(1) 的小樂

            Job Hunting

            公告

            記錄我的生活和工作。。。
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            統(tǒng)計(jì)

            • 隨筆 - 182
            • 文章 - 1
            • 評論 - 41
            • 引用 - 0

            留言簿(10)

            隨筆分類(70)

            隨筆檔案(182)

            文章檔案(1)

            如影隨形

            搜索

            •  

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            POJ 2524 并查集

            之前這個(gè)問題用深度優(yōu)先搜索做的。。耗時(shí)很長,很顯然這是一個(gè)并查集的題目:

            #include<stdio.h>
            #include<vector>
            #include<algorithm>
            using namespace std;
            vector <int> a[50001];
            int n,m,col;
            bool v[50001];
            void dfs(int k)
            {
                int i,j;
                v[k]=1;
                for(i=0;i<a[k].size();i++)
                    if(v[a[k][i]]==0)dfs(a[k][i]);
            }    
            int main()
            {
                int i,j,p,q,cn=0;
                while(scanf("%d %d",&n,&m),n||m)
                {
                    for(i=1;i<=n;i++)a[i].clear(),v[i]=0;
                    for(i=0;i<m;i++)scanf("%d %d",&p,&q),a[p].push_back(q),a[q].push_back(p);
                    col=0;
                    for(i=1;i<=n;i++)if(v[i]==0)dfs(i),col++;
                    printf("Case %d: %d\n",++cn,col);    
                }    
                return 0;
            }    

             

             

            并查集版本:

            #include <iostream>
            using namespace std;

            #define MAXN 500001
            struct
            {
                 int parent;
                 int rank;
            }UFS[MAXN];          //UnionFindSet   UFS

            //其中Parent為正數(shù)時(shí)表示該節(jié)點(diǎn)的父節(jié)點(diǎn)下標(biāo),為負(fù)數(shù)時(shí)表示該節(jié)點(diǎn)為一個(gè)根節(jié)點(diǎn),其絕對值為該集合包含的節(jié)點(diǎn)總數(shù)。
            //rank表示權(quán)值,在不同問題中有不同的含義。

            void MakeSet(int N)     /* 初始化 */
            {
                 int i;

                 for(i=0;i<=N;i++)      //額外增加一位,從0開始可以從1開始也可以
                 {
                     UFS[i].parent=-1;  /* 開始每個(gè)節(jié)點(diǎn)單獨(dú)構(gòu)成一個(gè)集合 */
                     UFS[i].rank=0;     /* 權(quán)值視具體情況付初值 */
                 }
            }

            int Root(int x)     /* 查找包含接點(diǎn)x的集合的根節(jié)點(diǎn) */

            {
                 int i=x,temp;
                 while(UFS[i].parent>0)
                     i=UFS[i].parent;

                 while(i!=x)     /* 壓縮路徑以提高以后檢索效率 */
                 {
                     temp=UFS[x].parent;            
                     UFS[x].parent=i;               //直接將x的祖先命為根節(jié)點(diǎn)
                     x=temp;                                 //繼續(xù)處理x的原祖先
                 }
                 return i;
            }

            void Union1(int a,int b)     /* 合并a和b所在的集合 */
            {
                 int fa,fb;
                 fa=Root(a);
                 fb=Root(b);
                 if(fa==fb) return;

                 if(UFS[fa].parent<UFS[fb].parent)     /* 始終將較小樹作為較大樹的子樹 */
                 {
                     UFS[fa].parent+=UFS[fb].parent;
                     UFS[fb].parent=fa;
                 }
                 else
                 {
                     UFS[fb].parent+=UFS[fa].parent;
                     UFS[fa].parent=fb;
                 }
            }
            void Union2(int a, int b)     //將rank較大的作為父節(jié)點(diǎn)
            {
                int x = Root(a), y = Root(b);
                if( x == y ) return ;
                if( UFS[x].rank > UFS[y].rank ) UFS[y].parent = x;
                else{
                    UFS[x].parent = y;
                    if( UFS[x].rank == UFS[y].rank ) UFS[y].rank++;
                }
            }

            int main()
            {
                int N, M, a, b;
                int nCases = 1;
                while(scanf("%d %d", &N, &M) && (M||N))
                {
                    MakeSet(N);
                    for(int i=1; i<=M; ++i)
                    {
                        scanf("%d %d", &a, &b);
                        a = Root(a);
                        b = Root(b);
                        //如果a,b不在同一個(gè)集合,則合并
                        if(a != b)
                        {
                            N--;
                            Union2(a, b);
                        }
                    }
                    printf("Case %d: %d\n", nCases++, N);
                }
                return 0;
            }

            今天明天總結(jié)一下并查集的相關(guān)知識(shí)吧!

            posted on 2010-09-27 22:41 Sosi 閱讀(523) 評論(0)  編輯 收藏 引用

            統(tǒng)計(jì)系統(tǒng)
            国产高清美女一级a毛片久久w| 一本大道久久香蕉成人网| 久久亚洲sm情趣捆绑调教| 女同久久| 欧美日韩成人精品久久久免费看| 日韩精品国产自在久久现线拍| 久久婷婷久久一区二区三区| 99久久99久久| 大香网伊人久久综合网2020| 久久久久久免费一区二区三区| www.久久精品| 国产精品热久久无码av| 品成人欧美大片久久国产欧美...| 国产成人精品久久一区二区三区av| 婷婷综合久久中文字幕| 久久精品人妻一区二区三区| 久久无码国产| 人妻少妇久久中文字幕一区二区 | 久久精品亚洲中文字幕无码麻豆| 亚洲日本va中文字幕久久| 久久久无码人妻精品无码| 一本久久久久久久| 久久午夜免费视频| 国产成人精品久久二区二区| 精品久久久久久久久久久久久久久 | 久久精品99无色码中文字幕| 午夜精品久久久久9999高清| 亚洲色大成网站www久久九| 国产成人精品久久免费动漫| 久久一区二区三区99| 久久国产亚洲精品无码| 日韩久久久久中文字幕人妻| 久久精品麻豆日日躁夜夜躁| 久久精品亚洲男人的天堂| 综合人妻久久一区二区精品| 久久国产精品一区| 久久久av波多野一区二区| 亚洲欧洲中文日韩久久AV乱码| 久久九九全国免费| 久久综合综合久久综合| 久久综合亚洲鲁鲁五月天|