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

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            亚洲女久久久噜噜噜熟女| 久久久久女教师免费一区| 久久青青草视频| 东方aⅴ免费观看久久av| 精品人妻伦九区久久AAA片69| 伊人久久综合成人网| 久久久久亚洲av无码专区| 夜夜亚洲天天久久| 亚洲国产成人久久综合区| 狠狠色综合网站久久久久久久高清 | 亚州日韩精品专区久久久| 亚洲日韩欧美一区久久久久我 | 999久久久国产精品| 香蕉99久久国产综合精品宅男自| 久久午夜夜伦鲁鲁片免费无码影视| 久久久久久夜精品精品免费啦| 麻豆精品久久精品色综合| 国产精品久久久久久五月尺| 久久99精品久久久久久久久久| 久久毛片一区二区| 一本久久久久久久| 嫩草伊人久久精品少妇AV| 欧美亚洲日本久久精品| 2021久久精品国产99国产精品| 久久国产色av免费看| 久久久久国产精品麻豆AR影院 | 国产亚州精品女人久久久久久 | 久久久久久极精品久久久| 久久精品亚洲中文字幕无码麻豆| 国产精品日韩深夜福利久久| 国产麻豆精品久久一二三| 久久国内免费视频| 无码任你躁久久久久久久| 久久99精品久久久久久水蜜桃| 99麻豆久久久国产精品免费| 亚洲色大成网站www久久九| 久久久久国产精品嫩草影院| 天堂无码久久综合东京热| 久久久久亚洲精品无码网址| 国产69精品久久久久9999| 久久福利青草精品资源站|