• <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 閱讀(260) 評論(0)  編輯 收藏 引用
            欧美精品国产综合久久| 久久99热这里只有精品国产| 狠狠色丁香婷婷久久综合| 无码任你躁久久久久久老妇| 久久久久亚洲AV无码专区首JN | 久久99精品国产麻豆婷婷| 久久影视国产亚洲| 色偷偷久久一区二区三区| 日本久久久精品中文字幕| 亚洲伊人久久成综合人影院| 人妻少妇久久中文字幕一区二区| 国产∨亚洲V天堂无码久久久| 久久综合成人网| 久久A级毛片免费观看| 亚洲国产精品无码久久青草| 午夜不卡久久精品无码免费| 久久免费香蕉视频| 99久久免费国产精精品| 久久99久久99精品免视看动漫| 久久精品国产免费一区| 亚洲va久久久噜噜噜久久天堂| 久久精品国产99久久久香蕉| 久久精品国产亚洲欧美| 久久国产精品99国产精| 久久久久精品国产亚洲AV无码| 久久久久亚洲AV无码专区网站 | 久久久久人妻一区精品| 国产精品久久自在自线观看| 亚洲va中文字幕无码久久不卡| 欧美日韩精品久久久久| 91精品国产91热久久久久福利| 色综合久久久久无码专区| 久久久久亚洲AV成人网人人网站| 久久亚洲精品无码播放| 久久国产一片免费观看| 久久福利片| 欧美性猛交xxxx免费看久久久| 久久久青草青青国产亚洲免观| 国产福利电影一区二区三区久久久久成人精品综合 | 无码任你躁久久久久久老妇App| 亚洲午夜久久久|