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

            M.J的blog

            algorithm,ACM-ICPC
            隨筆 - 39, 文章 - 11, 評論 - 20, 引用 - 0
            數(shù)據(jù)加載中……

            POJ The Suspects(并查集)

            又是一個并查集,題意大概是N個學(xué)生,學(xué)生0是SARS疑似,學(xué)生分為M組,一個學(xué)生可以屬于不同組,只要和疑似學(xué)生在一組,自己也就成了疑似,問最后又多少學(xué)生是疑似病例。
            Code:

             1 #include<stdio.h>
             2 #define MAX 30002
             3 int m,n;
             4 struct type
             5 {
             6     int father,v;
             7 }a[MAX];
             8 void initial(int n)
             9 {
            10     int i;
            11     for(i=0;i<n;i++){
            12         a[i].father=i;
            13         a[i].v=1;
            14     }
            15 }
            16 int find(int n)
            17 {
            18     if(a[n].father!=n)
            19         return find(a[n].father);
            20     return n;
            21 }
            22 void Union(int root1,int root2)
            23 {
            24     int t1,t2;
            25     t1=find(root1);
            26     t2=find(root2);
            27     if(t1==t2) return ;
            28     if(t1!=t2){
            29         if(a[t1].v<a[t2].v){
            30             a[t1].father=t2;
            31             a[t2].v+=a[t1].v;
            32         }
            33         else{
            34             a[t2].father=t1;
            35             a[t1].v+=a[t2].v;
            36         }
            37     }
            38 }
            39 int main()
            40 {
            41     int cas,i,j,k,p,q,N,M;
            42     while(scanf("%d%d",&N,&M)!=EOF){
            43         if(N==0&&M==0break;
            44         initial(N);
            45         for(i=1;i<=M;i++){
            46             scanf("%d",&k);
            47             scanf("%d",&p);
            48             for(j=2;j<=k;j++){
            49                 scanf("%d",&q);
            50                 Union(p,q);
            51             }
            52         }
            53         k=find(0);
            54         printf("%d\n",a[k].v);
            55     }
            56     
            57 
            58 }

            posted on 2010-04-24 15:06 M.J 閱讀(173) 評論(0)  編輯 收藏 引用


            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            久久久精品国产免大香伊| 99久久精品免费看国产一区二区三区| 国产精品久久久久久久app| 粉嫩小泬无遮挡久久久久久| 色综合久久无码中文字幕| 色综合久久久久久久久五月| 久久午夜无码鲁丝片秋霞 | 国产三级精品久久| 久久99精品国产99久久6男男| 色欲久久久天天天综合网| 少妇精品久久久一区二区三区| 久久久无码精品亚洲日韩蜜臀浪潮 | 中文字幕无码精品亚洲资源网久久 | 久久久91精品国产一区二区三区| 久久久亚洲欧洲日产国码二区| 精品一区二区久久久久久久网站| 国产成人精品久久一区二区三区av| 国产真实乱对白精彩久久| 久久一本综合| 久久久久成人精品无码中文字幕| 无码国产69精品久久久久网站| 久久久久久国产精品免费无码 | 99久久精品国产综合一区| 久久国产福利免费| 久久婷婷五月综合色奶水99啪| 一本一道久久综合狠狠老| 国产精品久久久久久久久| 久久精品一区二区影院| 亚洲国产精品无码久久一区二区| 国产精品久久久久久福利漫画| 久久久久九九精品影院| 久久人人爽人人爽人人AV | 精品国产91久久久久久久a | 97久久精品人人澡人人爽| 久久久久久久久久久久中文字幕 | 久久精品成人免费网站| 国产精品久久久亚洲| 久久精品国产亚洲77777| 久久久久久国产精品无码超碰| 99久久精品国内| 午夜福利91久久福利|