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

            閱讀排行榜

            久久精品一区二区三区不卡| 亚洲色大成网站WWW久久九九| 亚洲精品tv久久久久久久久久| 成人国内精品久久久久一区| 亚洲综合伊人久久大杳蕉| 久久精品成人欧美大片| 18岁日韩内射颜射午夜久久成人| 国产人久久人人人人爽| 久久久久AV综合网成人| 久久久久成人精品无码中文字幕 | 精品久久久久久| 久久人妻少妇嫩草AV无码专区| 久久福利资源国产精品999| 久久久久久久久66精品片| 亚洲精品99久久久久中文字幕| 香蕉99久久国产综合精品宅男自 | 亚洲日本久久久午夜精品| 色播久久人人爽人人爽人人片aV| 91久久精品国产91性色也| 精品无码人妻久久久久久| 久久婷婷五月综合97色直播| 性欧美大战久久久久久久| 亚洲精品无码久久千人斩| 成人妇女免费播放久久久| 国内精品久久久久久久久| 日本国产精品久久| 亚洲综合日韩久久成人AV| 91久久精品91久久性色| 久久99精品国产99久久6| 亚洲欧洲精品成人久久曰影片| 婷婷国产天堂久久综合五月| 久久夜色精品国产欧美乱| 国内精品久久久久久久影视麻豆| 久久婷婷国产剧情内射白浆| 99久久精品国产免看国产一区| 精品久久久无码中文字幕天天| 亚洲国产另类久久久精品小说 | 久久综合给合综合久久| 国产aⅴ激情无码久久| 91精品国产91久久久久久| 久久精品亚洲AV久久久无码|