• <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
            }
            精品久久久久中文字| 久久只有这精品99| 91精品国产91久久综合| 91精品国产色综合久久| 久久免费精品视频| 亚洲а∨天堂久久精品| 久久久久久综合网天天| 久久亚洲AV成人无码国产| 久久国内免费视频| 国产精品一区二区久久不卡| 69SEX久久精品国产麻豆| 久久九九免费高清视频| 久久99毛片免费观看不卡| 久久高潮一级毛片免费| 亚洲综合伊人久久综合| 国产成人无码精品久久久免费 | 久久国产三级无码一区二区| 久久人人爽人人人人爽AV| 欧美精品一区二区精品久久 | 久久精品国产清高在天天线| 欧美激情精品久久久久久| 999久久久免费精品国产| 成人综合久久精品色婷婷| 7国产欧美日韩综合天堂中文久久久久| 久久午夜免费视频| 久久久久女教师免费一区| 日本精品久久久久中文字幕| 久久精品毛片免费观看| 久久精品国产99国产精品亚洲| 久久无码人妻精品一区二区三区 | 亚洲欧美一区二区三区久久| 久久久久久久尹人综合网亚洲| 无码人妻精品一区二区三区久久久 | 亚洲精品午夜国产va久久| 日韩va亚洲va欧美va久久| 99久久国产热无码精品免费久久久久| av午夜福利一片免费看久久| 久久精品无码专区免费青青| 久久影视综合亚洲| 久久久久人妻一区二区三区 | 亚洲精品美女久久久久99小说|