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

            Why so serious? --[NKU]schindlerlee

            2010年02月07日星期日.sgu172 判斷一個(gè)圖是否是二分圖 黑白染色

            2010年02月07日星期日.sgu172 判斷一個(gè)圖是否是二分圖 黑白染色
            題意解釋:給出一個(gè)圖的邊,對這個(gè)圖進(jìn)行黑白染色,不能染色則輸出no
            能染色輸出黑色或者白色的個(gè)數(shù),并且輸出點(diǎn)的序號
             1 
             2 const int N = 256;
             3 int g[N][N],n,m,vis[N];
             4 const int black = 1;
             5 const int white = 2;
             6 int res ;
             7 
             8 bool dfs(int u,int color)
             9 {
            10   vis[u] = color;
            11   if (color == black) { res++; }
            12   if (color == black) { color = white; }
            13   else { color = black; }
            14 
            15   int i;
            16   for (i = 1;i <= n;i++) {
            17       if (g[u][i]) {
            18           if (vis[i] == 0) {
            19               if(!dfs(i,color)) return false;
            20           }else if (vis[i] != 0 && vis[i] != color) {
            21               return false;
            22           }
            23       }
            24   }
            25   return true;
            26 }
            27 
            28 bool dyeing()
            29      //染色
            30 {
            31   for (int i = 1;i <= n;i++) {
            32       if (vis[i] == 0) {
            33           if(!dfs(i,black)) {
            34               return false;
            35           }
            36       }
            37   }
            38   return true;
            39 }
            40 
            41 int main()
            42 {
            43   int i,j,k,a,b;
            44   scanf("%d %d",&n,&m);
            45   for (i = 0;i < m;i++) {
            46       scanf("%d%d",&a,&b);
            47       g[a][b] = g[b][a] = 1;
            48   }
            49   if (!dyeing()) {
            50       printf("no\n");
            51   }else {
            52       printf("yes\n");
            53       printf("%d\n",res);
            54       for (i = 1;i <= n;i++) {
            55           if (vis[i] == black) {
            56               printf("%d ",i);
            57           }
            58       }
            59       printf("\n");
            60   }
            61   return 0;
            62 }
            63 


            posted on 2010-02-07 20:00 schindlerlee 閱讀(1521) 評論(0)  編輯 收藏 引用 所屬分類: 解題報(bào)告

            久久综合亚洲色HEZYO社区 | 久久国产劲爆AV内射—百度| 欧美日韩精品久久久免费观看| 久久精品一本到99热免费| 午夜精品久久久久久中宇| 嫩草影院久久99| 亚洲AV日韩AV天堂久久| 99久久国产综合精品网成人影院 | 久久精品国产亚洲AV影院| 熟妇人妻久久中文字幕| 国产精品gz久久久| 久久精品国产亚洲αv忘忧草| 一本久久久久久久| 久久精品日日躁夜夜躁欧美| 国产一区二区精品久久岳| www.久久热| 无码国内精品久久人妻蜜桃| 深夜久久AAAAA级毛片免费看| 久久久久久久综合日本亚洲| 色欲av伊人久久大香线蕉影院| 久久99精品久久久久久野外| AAA级久久久精品无码片| 久久精品免费一区二区| 欧美精品九九99久久在观看| 久久国产视频网| 激情综合色综合久久综合| 97久久综合精品久久久综合| 久久精品国产亚洲av日韩| 99久久精品免费看国产一区二区三区| 精品久久久久久久中文字幕 | 久久久久这里只有精品| 99久久99久久精品国产| 久久久久夜夜夜精品国产| 精品久久久久久中文字幕| 久久精品国产亚洲沈樵| 久久99中文字幕久久| 一本大道久久a久久精品综合 | 久久人人爽人人爽人人AV东京热 | 久久er国产精品免费观看8| 精品久久久久久久久中文字幕| 狠狠狠色丁香婷婷综合久久俺|