• <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)論排行榜

            日韩一区二区久久久久久| 精品国产综合区久久久久久| 亚洲国产一成久久精品国产成人综合| 99久久国产免费福利| 久久午夜福利电影| 狠狠精品久久久无码中文字幕| 亚洲AV无码久久精品成人| 粉嫩小泬无遮挡久久久久久| 青青国产成人久久91网| 午夜福利91久久福利| 无码人妻精品一区二区三区久久| 久久精品嫩草影院| 波多野结衣久久| 国产午夜福利精品久久| 亚洲国产欧洲综合997久久| 国产成人精品久久综合| 久久亚洲精品成人AV| 久久丝袜精品中文字幕| 成人国内精品久久久久影院| 久久午夜免费视频| 狠狠色综合网站久久久久久久 | 久久超乳爆乳中文字幕| 伊人久久精品线影院| 蜜臀av性久久久久蜜臀aⅴ| 久久乐国产综合亚洲精品| 国产免费久久久久久无码| 狠狠色丁香婷婷综合久久来| 久久夜色精品国产欧美乱| 精品人妻伦九区久久AAA片69| 久久久不卡国产精品一区二区| 99久久婷婷国产综合亚洲| 色欲久久久天天天综合网| 热久久最新网站获取| 久久久久久国产a免费观看不卡 | 精品免费久久久久国产一区| 色综合久久无码中文字幕| 亚洲国产另类久久久精品黑人| 国内精品伊人久久久久妇| 久久综合亚洲鲁鲁五月天| 国产精品成人久久久| 亚洲美日韩Av中文字幕无码久久久妻妇|