• <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>
            隨筆-65  評論-6  文章-0  trackbacks-0
             1 /*
             2 Author:    Leo.W
             3 Descriptipn:  一個垃圾郵件判別系統。M a b 表示a、b具有相同內容,S a 表示對a存在誤判,求最后內容相同郵件集合的數目。
             4 How to Do:    并查集,加入了一個新的操作是集合節點的刪除,但由于集合內部元素關系的傳遞性,因此刪除元素但保留由此元素
             5               帶來的關系。所以不必刪除結點,直接改頭換面讓被刪除的結點在隊末出現,重新開始,因此就用到了id數組。
             6   */
             7 #include <cstdio>
             8 #include <cstdlib>
             9 #define MAXSIZE 1000002
            10 int n,m;//n個結點,m條路
            11 int par[MAXSIZE],id[MAXSIZE],hasChild[MAXSIZE];
            12 char ch;
            13 
            14 int findSet(int x){
            15     if(x!=par[x])
            16         par[x]=findSet(par[x]);
            17     return par[x];
            18 }
            19 inline void merge(int x,int y){
            20     x=findSet(x);
            21     y=findSet(y);
            22     if(x==y) return;
            23     par[x]=y;//x變成附屬
            24     hasChild[y]+=hasChild[x];
            25     hasChild[x]=0;//表示x只是y領銜的集合的一員
            26 }
            27 inline void makeSet(int n){
            28     int i;
            29     for(i=0;i<n;i++)//從0到n-1
            30         par[i]=i,id[i]=i,hasChild[i]=1;
            31 }
            32 inline void scan(int &x){
            33     while (ch=getchar(),ch<'0'||ch>'9');x=ch-'0';
            34     while (ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-'0';
            35 }
            36 int main(){
            37     //freopen("in.txt","r",stdin);
            38     int no=1;
            39     while (true){
            40         scan(n);scan(m);
            41         if(n==0&&m==0)    break;
            42         makeSet(n);
            43         int i,j;  int total=n;//用于隊末擴展
            44         char str;    int a,b;
            45         for(i=0;i<m;i++){
            46             str=getchar();
            47             scan(a);
            48             if(str=='M'){            
            49                 scan(b);
            50                 merge(id[a],id[b]);
            51                 continue;
            52             }
            53             int fa=findSet(id[a]);
            54             hasChild[fa]--;//原屬集合內部元素數減少
            55             id[a]=total;//映射被刪除的結點,以后對a的操作,轉為對total的操作
            56             par[total]=total;//自立門戶,即單獨一個集合
            57             hasChild[total]=1;
            58             id[total]=total;//擴展方便最后統計
            59             total++;
            60         }
            61         int sum=0;
            62         for(j=0;j<total;j++)
            63             if(hasChild[j]>0)    sum++;
            64         printf("Case #%d: %d\n",no++,sum);
            65     }    
            66     return 0;
            67  }
            68 
            posted on 2012-03-17 22:27 Leo.W 閱讀(259) 評論(0)  編輯 收藏 引用
            久久亚洲精品成人AV| 日本久久中文字幕| AV狠狠色丁香婷婷综合久久| 综合网日日天干夜夜久久| 久久A级毛片免费观看| 国内精品久久久久久久久| 久久综合久久美利坚合众国| 色狠狠久久AV五月综合| 久久国产精品久久| 久久久久国产精品嫩草影院| 精品久久久久久综合日本| 久久久久久久久66精品片| 久久国产精品久久| 一本一道久久综合狠狠老| 久久久久国产一区二区| 国产日产久久高清欧美一区| 女人高潮久久久叫人喷水| 国产精品九九久久免费视频| 久久精品国产亚洲AV无码麻豆 | 国産精品久久久久久久| 亚洲欧洲日产国码无码久久99| 国产99久久九九精品无码| 久久精品无码一区二区无码| 一级做a爰片久久毛片看看| 精品久久久久中文字| 国产日产久久高清欧美一区| 久久久精品2019免费观看| 久久久久人妻一区二区三区| 人妻系列无码专区久久五月天| 精品久久久久久久久久中文字幕 | 狠狠色婷婷久久综合频道日韩 | 久久久无码人妻精品无码| 久久妇女高潮几次MBA| 久久人人爽人人爽人人片AV不| 日日狠狠久久偷偷色综合96蜜桃 | 久久精品桃花综合| 亚洲国产天堂久久久久久| 久久综合一区二区无码| 亚洲国产精品成人AV无码久久综合影院| 品成人欧美大片久久国产欧美| 伊人久久大香线焦综合四虎|