• <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>
            posts - 195,  comments - 30,  trackbacks - 0

            Description

            Description

            Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strategy is to separate the suspects from others.
            In the Not-Spreading-Your-Sickness University (NSYSU), there are many student groups. Students in the same group intercommunicate with each other frequently, and a student may join several groups. To prevent the possible transmissions of SARS, the NSYSU collects the member lists of all student groups, and makes the following rule in their standard operation procedure (SOP).
            Once a member in a group is a suspect, all members in the group are suspects.
            However, they find that it is not easy to identify all the suspects when a student is recognized as a suspect. Your job is to write a program which finds all the suspects.

            Input

            The input file contains several cases. Each test case begins with two integers n and m in a line, where n is the number of students, and m is the number of groups. You may assume that 0 < n <= 30000 and 0 <= m <= 500. Every student is numbered by a unique integer between 0 and n−1, and initially student 0 is recognized as a suspect in all the cases. This line is followed by m member lists of the groups, one line per group. Each line begins with an integer k by itself representing the number of members in the group. Following the number of members, there are k integers representing the students in this group. All the integers in a line are separated by at least one space.
            A case with n = 0 and m = 0 indicates the end of the input, and need not be processed.

            Output

            For each case, output the number of suspects in one line.

            Sample Input

            100 4
            2 1 2
            5 10 13 11 12 14
            2 0 1
            2 99 2
            200 2
            1 5
            5 1 2 3 4 5
            1 0
            0 0

            Sample Output

            4
            1
            1

            啟示1,一定注意初始化帶來的影響,1,是什么地方初始化,2,前一個(gè)case不應(yīng)當(dāng)對(duì)下一個(gè)造成影響
                    2,有層次性的問題一定要處理好,不要
                    3,例如重復(fù)數(shù)據(jù)不能重復(fù)初始化。
                                      cin>>t;
                                       if(father[t]<0)//必不可少
                                         father[t]=t;


            #include<iostream>
            #include<cstdlib>
            using namespace std;
              int rank[30001];
              int father[30001];
              void UNION(int a,int b)
              {
              if(a==b)return;
              else
              {
               if(rank[a]<rank[b])
               {
                father[b]=father[a];
                  }
               else
               {
                father[a]=father[b];
               } 
              }
              
              }
              int Find(int t)
              {
              int tmp=t,x;
              while(father[tmp]!=tmp)
              {
               tmp=father[tmp];
              }
              
              while(t!=father[t])
              {
                  x=t;
                  t=father[x];
               father[x]=tmp;
                 } 

                 return t;
              }
              int main()
              {
              freopen("s.txt","r",stdin);
              freopen("key.txt","w",stdout);
              int i,j,nt,t1,t,result;
              while(cin>>i>>j,i||j)
              {
              result=0;
              memset(rank,1,sizeof(rank));
              memset(father,-1,sizeof(father));
              rank[0]=0;
              father[0]=0;
             for(int k=0;k<j;k++)
             {
              cin>>nt;
              cin>>t1;
              rank[t1]=t1;
              if(father[t1]<0)
                father[t1]=t1;
              for(int m=1;m<nt;m++)
              {
               cin>>t;
               rank[t]=t;
               if(father[t]<0)
                father[t]=t;
               UNION(Find(t1),Find(t));
              }
             }
             for(int l=0;l<i;l++)
             {
              if(father[l]>=0)
              {
               if(!Find(l))
              result++;
                 }
             }
             cout<<result<<endl;
              
              }

              //system("PAUSE");
              return   0;
              }

            posted on 2009-07-03 16:51 luis 閱讀(686) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 并查集*哈希表*類似
            <2010年12月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            久久久久亚洲av成人无码电影| 中文字幕乱码久久午夜| 久久线看观看精品香蕉国产| 久久97精品久久久久久久不卡| 青草影院天堂男人久久| 久久久久这里只有精品| 麻豆一区二区99久久久久| 国产午夜精品理论片久久影视| 国产91久久综合| 色欲av伊人久久大香线蕉影院| 69国产成人综合久久精品| 亚洲国产成人久久综合区| 久久国产精品成人影院| 久久精品中文字幕第23页| 久久久久亚洲AV无码麻豆| 欧美一区二区久久精品| 2020最新久久久视精品爱 | 久久久久亚洲精品天堂| 久久亚洲国产成人影院网站| 久久综合狠狠综合久久| 欧美久久一区二区三区| 香港aa三级久久三级| 国产麻豆精品久久一二三| 国产亚洲精品久久久久秋霞| 久久国产免费直播| 青青草原综合久久| 久久精品国产亚洲AV电影| 亚洲乱码精品久久久久..| 香蕉久久永久视频| 色天使久久综合网天天| 久久99精品久久久久久秒播| 青青草国产精品久久| 久久综合综合久久狠狠狠97色88| 久久综合精品国产二区无码| 99精品国产综合久久久久五月天| 亚洲一区精品伊人久久伊人| 亚洲欧美日韩精品久久亚洲区 | 99久久这里只精品国产免费| 久久影院久久香蕉国产线看观看| 精品乱码久久久久久夜夜嗨| 狠狠精品久久久无码中文字幕|