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

            poj 2524 Ubiquitous Religions 【并查集】

            Ubiquitous Religions
            Time Limit: 5000MS Memory Limit: 65536K
            Total Submissions: 12445 Accepted: 5900

            Description

            There are so many different religions in the world today that it is difficult to keep track of them all. You are interested in finding out how many different religions students in your university believe in.

            You know that there are n students in your university (0 < n <= 50000). It is infeasible for you to ask every student their religious beliefs. Furthermore, many students are not comfortable expressing their beliefs. One way to avoid these problems is to ask m (0 <= m <= n(n-1)/2) pairs of students and ask them whether they believe in the same religion (e.g. they may know if they both attend the same church). From this data, you may not know what each person believes in, but you can get an idea of the upper bound of how many different religions can be possibly represented on campus. You may assume that each student subscribes to at most one religion.

            Input

            The input consists of a number of cases. Each case starts with a line specifying the integers n and m. The next m lines each consists of two integers i and j, specifying that students i and j believe in the same religion. The students are numbered 1 to n. The end of input is specified by a line in which n = m = 0.

            Output

            For each test case, print on a single line the case number (starting with 1) followed by the maximum number of different religions that the students in the university believe in.

            Sample Input

            10 9
            1 2
            1 3
            1 4
            1 5
            1 6
            1 7
            1 8
            1 9
            1 10
            10 4
            2 3
            4 5
            4 8
            5 8
            0 0
            

            Sample Output

            Case 1: 1
            Case 2: 7
            第一個(gè)并查集程序,最小生成樹不算。
             n個(gè)點(diǎn),給你m條邊,求最大能有多少個(gè)連通分量。
            #include<iostream>
            using namespace std;
            const int MAX=50001;
            int fa[MAX];

            int find(int x)
            {
                
            return fa[x]==x?x:find(fa[x]);
            }

            void Union(int x, int y)
            {
                 fa[find(x)]
            =find(y);
            }
            int main()
            {
                
            int n,m;
                
            for(int tt=1; ; tt++)
                { 
                          cin
            >>n>>m;
                         
            if( n==0&&m==0)break;
                         
                         
            for(int i=1; i<=n; i++)
                                 fa[i]
            =i; 
                                 
                         
            int max=n;              
                         
            for(int i=1,s,t; i<=m; i++)
                                 {
                                     cin
            >>s>>t;
                                     
            if(find(s)!=find(t))max=max-1;
                                     Union(s,t);              
                                 }
                                 
                         cout
            <<"Case "<<tt<<':'<<' '<<max<<endl;
                         
                }
                
                system(
            "pause");    
                
            return 0;
            }


            posted on 2010-08-26 19:20 田兵 閱讀(319) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 算法筆記

            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            導(dǎo)航

            統(tǒng)計(jì)

            常用鏈接

            留言簿(2)

            隨筆分類(65)

            隨筆檔案(65)

            文章檔案(2)

            ACM

            搜索

            積分與排名

            最新隨筆

            最新評(píng)論

            閱讀排行榜

            日本精品久久久久久久久免费| 亚洲人成精品久久久久| 97精品国产97久久久久久免费| 亚洲第一永久AV网站久久精品男人的天堂AV | 精品一二三区久久aaa片| 久久人人爽人人爽人人AV东京热| 99久久人人爽亚洲精品美女| 一本综合久久国产二区| 久久久国产精品福利免费| 欧美一区二区久久精品| 亚洲乱亚洲乱淫久久| 亚洲乱码日产精品a级毛片久久| 波多野结衣久久| 久久人人爽人人爽人人av东京热| 久久久久久亚洲Av无码精品专口| 波多野结衣久久一区二区| 国产成人久久AV免费| 久久人妻少妇嫩草AV蜜桃| 久久精品国产免费| 久久国产欧美日韩精品| 久久久久久国产精品无码下载| 久久精品国产免费一区| 中文字幕无码久久精品青草| 国内精品久久久久久99蜜桃 | 久久亚洲国产精品五月天婷| 久久香蕉一级毛片| 亚洲日本va中文字幕久久| 国产精品热久久无码av| 久久综合国产乱子伦精品免费| 久久国产精品无码网站| 狠色狠色狠狠色综合久久| 久久精品国产亚洲AV蜜臀色欲 | 狠狠色丁香久久婷婷综合_中 | 久久久亚洲AV波多野结衣| 国产99久久久国产精免费| 国内精品久久国产大陆| 久久亚洲美女精品国产精品| 婷婷综合久久中文字幕蜜桃三电影| 久久亚洲精品无码aⅴ大香| 要久久爱在线免费观看| 久久人人爽人人爽人人片AV麻豆|