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

            ACM___________________________

            ______________白白の屋
            posts - 182, comments - 102, trackbacks - 0, articles - 0
            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(24)

            隨筆分類(332)

            隨筆檔案(182)

            FRIENDS

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            自己的 并查集 模板

            Posted on 2010-08-10 11:36 MiYu 閱讀(530) 評論(0)  編輯 收藏 引用 所屬分類: ACM ( 并查集 )ACM ( MST 最小生成樹 )
            MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋

            剛剛學習完并查集的基礎知識.. 自己寫了3個模板類 . 發上和大家分享下:

            MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋

            #include 
            <iostream>
            using namespace std;
            typedef 
            class arrUFS{
                   
            public:
                          arrUFS(
            int n = 0):N(n){ set = new int[n]; for ( int i = 0; i != N; ++ i) set[i] = i; };
                          
            ~arrUFS(){ delete [] set; };
                          
            int find ( int x ){ return set[x]; }
                          
            void Merge1( int a,int b){   int i = min(set[a],set[b]);
                                                       
            int j = max(set[a],set[b]);
                                                       
            for ( int k=1; k<=N; k++) {
                                                             
            if (set[k] == j)
                                                             
            set[k] = i;
                                                       }
                                                   }
                   
            private:
                          
            int *set;
                          
            int N;         
            }arrUFS; 
            // 數組形式

            //樹形并查集, 路徑壓縮 
            typedef struct {
                 
            int parent;
                 
            int cnt;   
            }Tset;  

            typedef 
            class treeUFS{
                   
            public:
                          treeUFS(
            int n = 0):N(n+2) { set = new Tset[N]; 
                                                      
            for ( int i = 0; i != N; ++ i) 
                                                      
            set[i].parent = i,set[i].cnt = 1
                                                    }
                          
            ~treeUFS(){ delete [] set; };
                          
            int find ( int x ){ int r = x; while ( set[r].parent != r ) //循環結束,則找到根節點
                                                                r = set[r],parent;       
                                                         
            int i = x;
                                                         
            while ( i != r) //本循環修改查找路徑中所有節點
                                                         {   
                                                             
            int j = set[i].parent;
                                                             
            set[i].parent = r;
                                                             i 
            = j;
                                                         } 
                                               
            return r;
                                            }
                          
            void Merge1( int x,int y ){  x = find ( x );  y = find ( y );  
                                                       
            if ( x == y ) return;
                                                       
            if ( set[x].cnt > set[y].cnt ){
                                                            
            set[y].parent = x;
                                                            
            set[x].cnt += set[y].cnt;
                                                       }
                                                       
            else{
                                                               
            set[x].parent = y;
                                                               
            set[y].cnt += set[x].cnt;        
                                                           }
                                                    }
                   
            private:
                          
            int *set;
                          
            int N;         
            }treeUFS; 
            // 樹形式  路徑壓縮 

            //屬性并查集, 帶樹深 
            typedef struct {
                 
            int parent;
                 
            int height;   
            }Tset;  

            typedef 
            class treeUFS{
                   
            public:
                          treeUFS(
            int n = 0):N(n+2) { set = new Tset[N];
                                                      visited 
            = new bool[N]; 
                                                      
            for ( int i = 0; i != N; ++ i) 
                                                      
            set[i].parent = i,set[i].height = 1,visited[i] = false
                                                    }
                          
            ~treeUFS(){ delete [] set; };
                          
            int find ( int x ){  int r = x;  while ( r != set[r].parent ) r = ser[r].parent;
                                               
            return r;
                                            }
                          
            void Merge1( int x,int y ){  x = find ( x );  y = find ( y );  
                                                       
            if ( x == y ) return;
                                                       
            if ( set[x].height == set[y].height ){
                                                            
            set[y].parent = x;
                                                            
            set[x].height ++;
                                                       }
                                                       
            else if ( set[x].height < set[y].height ) {
                                                                 
            set[x].parent = y;       
                                                               }
                                                       
            else{
                                                                 
            set[y].parent = x;
                                                           }
                                                    }
                   
            private:
                          
            int *set;
                          
            bool *visited;
                          
            int N;         
            }treeUFS; 
            // 樹形式 帶樹深 

            int main ()
            {
                
            return 0
            }
            久久久久久伊人高潮影院| 天天躁日日躁狠狠久久| 人妻无码αv中文字幕久久琪琪布 人妻无码久久一区二区三区免费 人妻无码中文久久久久专区 | 青青久久精品国产免费看| 亚洲国产成人久久综合区| 久久夜色精品国产噜噜亚洲AV| 久久精品中文騷妇女内射| 国产亚洲美女精品久久久| 热久久最新网站获取| 久久精品欧美日韩精品| 久久久九九有精品国产| 漂亮人妻被中出中文字幕久久 | 久久精品国产99国产精品亚洲| 久久精品麻豆日日躁夜夜躁| 久久精品人人做人人爽电影蜜月| 九九久久自然熟的香蕉图片| 久久久免费观成人影院| 久久er国产精品免费观看2| 久久精品中文字幕一区| 亚洲一区中文字幕久久| 亚洲午夜久久影院| 午夜精品久久久久久久| 欧美久久亚洲精品| 国产精品成人99久久久久| 久久亚洲精品视频| 久久人人妻人人爽人人爽| 久久久久无码中| 久久婷婷色综合一区二区| 99999久久久久久亚洲| 好属妞这里只有精品久久| 久久久亚洲裙底偷窥综合| 久久久久噜噜噜亚洲熟女综合| 99热成人精品热久久669| 久久综合88熟人妻| 久久亚洲精品成人AV| 亚洲精品乱码久久久久久自慰 | 久久婷婷国产剧情内射白浆| 国产99久久久久久免费看| 7国产欧美日韩综合天堂中文久久久久 | 麻豆成人久久精品二区三区免费 | 激情五月综合综合久久69|