• <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
            第一個并查集程序,最小生成樹不算。
             n個點,給你m條邊,求最大能有多少個連通分量。
            #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) 評論(0)  編輯 收藏 引用 所屬分類: 算法筆記

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

            導航

            統計

            常用鏈接

            留言簿(2)

            隨筆分類(65)

            隨筆檔案(65)

            文章檔案(2)

            ACM

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            久久婷婷综合中文字幕| 国产成人精品久久一区二区三区| 国产成人无码精品久久久免费 | 思思久久99热只有频精品66| 国内精品久久国产| 少妇久久久久久被弄高潮| 97久久超碰国产精品旧版| 久久精品国产清自在天天线| 久久精品一区二区三区AV| 久久精品国产69国产精品亚洲| 久久国产热这里只有精品| 欧美亚洲国产精品久久高清| 久久久久一区二区三区| 婷婷久久精品国产| 亚洲国产成人久久综合碰碰动漫3d | 亚洲人成电影网站久久| 人妻无码久久一区二区三区免费| 国产精品99久久久久久董美香| 久久婷婷五月综合97色直播| 国产激情久久久久影院老熟女| 人妻精品久久无码专区精东影业 | 久久中文字幕精品| 一级做a爰片久久毛片16| 亚洲午夜久久久久久噜噜噜| 久久久久综合网久久| 亚洲色欲久久久综合网| 亚洲精品成人网久久久久久| 91精品国产色综久久| 久久午夜伦鲁片免费无码| 波多野结衣久久精品| 久久久青草青青国产亚洲免观| 久久国产成人精品麻豆| 久久国产精品无码HDAV| 色综合久久久久久久久五月| 久久精品国产99国产精品亚洲| 久久丝袜精品中文字幕| 国产精品永久久久久久久久久| 久久99国产精品二区不卡| 久久久久久亚洲Av无码精品专口 | 久久久久噜噜噜亚洲熟女综合 | 国产免费久久精品99久久|