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

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

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

            題目地址:
                     http://acm.hdu.edu.cn/showproblem.php?pid=1213
            題目描述:
            How Many Tables

            Time Limit: 
            2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
            Total Submission(s): 
            2337    Accepted Submission(s): 1033


            Problem Description
            Today 
            is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers.

            One important rule 
            for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table.

            For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay 
            in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.
             

            Input
            The input starts with an integer T(
            1<=T<=25) which indicate the number of test cases. Then T test cases follow. Each test case starts with two integers N and M(1<=N,M<=1000). N indicates the number of friends, the friends are marked from 1 to N. Then M lines follow. Each line consists of two integers A and B(A!=B), that means friend A and friend B know each other. There will be a blank line between two cases.
             

            Output
            For each test 
            case, just output how many tables Ignatius needs at least. Do NOT print any blanks.
             

            Sample Input
            2
            5 3
            1 2
            2 3
            4 5

            5 1
            2 5
             

            Sample Output
            2
            4

            題目分析:
            并查集中的超級水題,  只要判斷集合的個數就可以了....................

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

            #include 
            <iostream>
            using namespace std;
            typedef 
            struct {
                 
            int parent;
                 
            int cnt;   
            }Tset;  

            typedef 
            struct treeUFS{
                   
            public:
                          treeUFS(
            int n = 0):N(n+1) { 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 init () { for ( int i = 0; i != N; ++ i) set[i].parent = i,set[i].cnt = 1;  }
                          
            int getSetCount ( int x ){ return set[ find(x) ].cnt; }
                          
            void Merge( 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:
                          Tset 
            *set;
                          
            int N;         
            }treeUFS;

            int main ()
            {
                
            int T;
                scanf ( 
            "%d",&T );
                
            while ( T -- )
                {
                       
            int N,M;
                       scanf ( 
            "%d%d",&N,&M );
                       treeUFS UFS ( N ); 
                       
            for ( int i = 1; i <= M; ++ i )
                       {
                             
            int a,b;
                             scanf ( 
            "%d%d",&a,&b );
                             UFS.Merge ( a,b ); 
                       }
                       
            int nCount = 0;
                       
            for ( int i = 1; i <= N; ++ i )
                       {
                            
            if ( UFS.find (i) == i )
                            {
                                 nCount 
            ++
                            }
                       } 
                       printf ( 
            "%d\n",nCount );
                }
                
            return 0
            }
            色偷偷888欧美精品久久久| 久久精品国产亚洲沈樵| 久久综合给合久久国产免费| 国产激情久久久久影院| 精品久久一区二区三区| 国产香蕉97碰碰久久人人| 国产99久久久国产精免费| 亚洲午夜无码AV毛片久久| 久久亚洲AV无码精品色午夜麻豆| 久久久久久亚洲精品不卡| 久久久久亚洲AV片无码下载蜜桃| 成人a毛片久久免费播放| 国内精品久久久久影院亚洲| 久久精品蜜芽亚洲国产AV| 人人狠狠综合久久亚洲高清| 久久精品国产亚洲AV忘忧草18| A级毛片无码久久精品免费| 久久精品国产福利国产琪琪| 色婷婷综合久久久中文字幕| 欧美精品丝袜久久久中文字幕| 久久久久人妻一区精品色| 亚洲国产天堂久久综合| 97久久精品人人做人人爽| 久久99国产精品一区二区| 久久久久亚洲av无码专区导航| 97香蕉久久夜色精品国产| 亚洲色婷婷综合久久| 久久久久av无码免费网| 欧美喷潮久久久XXXXx| 99久久精品无码一区二区毛片 | 88久久精品无码一区二区毛片| 狠狠色噜噜狠狠狠狠狠色综合久久| 久久A级毛片免费观看| 久久国产精品久久精品国产| 国产精品一区二区久久精品无码| 国产综合成人久久大片91| 亚洲国产精品无码久久久蜜芽 | 亚洲国产另类久久久精品黑人| 成人国内精品久久久久一区| 久久精品www人人爽人人| 欧美伊人久久大香线蕉综合69|