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

            閱讀排行榜

            欧美日韩精品久久久久| 色婷婷久久综合中文久久一本| 久久亚洲日韩看片无码| 亚洲中文字幕久久精品无码喷水| 久久精品免费一区二区| 久久久久人妻精品一区| 久久久久18| 精品久久久久久久国产潘金莲| 色诱久久久久综合网ywww| 99久久精品影院老鸭窝| 香蕉久久夜色精品国产2020| 久久久久AV综合网成人| 天天爽天天爽天天片a久久网| 亚洲第一永久AV网站久久精品男人的天堂AV | 青青草原1769久久免费播放| 91精品国产91久久久久久青草| 九九久久99综合一区二区| 色综合久久夜色精品国产| 久久精品国产精品国产精品污| 久久久久精品国产亚洲AV无码| 99久久人人爽亚洲精品美女| 久久午夜伦鲁片免费无码| 久久国产精品无| 久久精品亚洲欧美日韩久久| 国产美女久久精品香蕉69| 久久人妻少妇嫩草AV蜜桃| 日韩精品无码久久一区二区三| 日韩亚洲欧美久久久www综合网| 久久AV无码精品人妻糸列| 久久久不卡国产精品一区二区 | 久久久久人妻一区精品果冻| 国产精品视频久久| 久久久久亚洲AV无码永不| 欧美日韩久久中文字幕| 亚洲精品乱码久久久久久不卡| 精品无码久久久久久国产| 99久久www免费人成精品| 93精91精品国产综合久久香蕉| 国产成人综合久久综合| 久久精品这里热有精品| 国内精品伊人久久久久网站|