• <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
            }
            日韩美女18网站久久精品| 久久精品国产免费观看三人同眠| 久久婷婷五月综合色奶水99啪| 国产成人无码精品久久久久免费| AAA级久久久精品无码区| 久久高清一级毛片| 亚洲午夜久久久| 久久天天躁狠狠躁夜夜96流白浆| 99国产欧美久久久精品蜜芽| 色综合久久中文综合网| 日韩电影久久久被窝网| 日本强好片久久久久久AAA | 国产精品九九久久免费视频 | 久久er99热精品一区二区| 久久久久久久综合日本亚洲| 亚洲精品无码专区久久同性男| 少妇精品久久久一区二区三区| 久久精品无码一区二区app| 亚洲AV无码久久寂寞少妇| 久久精品成人免费国产片小草| 久久久久久无码Av成人影院| 欧美与黑人午夜性猛交久久久| 国产Av激情久久无码天堂| 青青青青久久精品国产| 久久精品国产黑森林| 91精品国产高清久久久久久国产嫩草| 国产精品久久久久乳精品爆| 久久香蕉超碰97国产精品| 婷婷久久综合九色综合绿巨人| 久久er热视频在这里精品| 久久精品九九亚洲精品| 久久久久高潮综合影院| 伊人热热久久原色播放www| 久久性精品| 久久久久亚洲爆乳少妇无| 精品国产热久久久福利| 91精品国产91久久久久久青草 | 国产精品成人99久久久久| 久久亚洲欧美日本精品| 色综合久久天天综合| 国产叼嘿久久精品久久|