• <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 判斷一個圖是否是二分圖 黑白染色

            2010年02月07日星期日.sgu172 判斷一個圖是否是二分圖 黑白染色
            題意解釋:給出一個圖的邊,對這個圖進行黑白染色,不能染色則輸出no
            能染色輸出黑色或者白色的個數,并且輸出點的序號
             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 閱讀(1527) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告

            久久人人爽人人澡人人高潮AV| 日本精品久久久久中文字幕8| 久久久久av无码免费网| 伊人久久大香线蕉AV色婷婷色| 亚洲AV日韩AV永久无码久久| 久久se精品一区二区| 狠狠色丁香久久婷婷综合| 四虎国产永久免费久久| 久久夜色精品国产| 国产精品美女久久久久久2018| 久久综合九色欧美综合狠狠| 久久久无码一区二区三区| 久久噜噜久久久精品66| 久久精品www人人爽人人| 性做久久久久久免费观看| 久久福利青草精品资源站| 亚洲人成精品久久久久| 欧美一级久久久久久久大| 婷婷综合久久中文字幕| 久久香综合精品久久伊人| 伊人伊成久久人综合网777| 国产激情久久久久影院| 久久国产精品一国产精品金尊| 免费精品国产日韩热久久| 日韩亚洲国产综合久久久| 国产免费久久精品丫丫| 久久精品www| 久久久久久久尹人综合网亚洲| 久久精品国产亚洲AV高清热| 久久天天躁狠狠躁夜夜躁2O2O| 久久精品国产亚洲av麻豆图片 | 伊人丁香狠狠色综合久久| 亚洲精品国精品久久99热一| 97精品依人久久久大香线蕉97| 亚洲日韩欧美一区久久久久我 | 国产精品久久波多野结衣| 国产精品久久久久aaaa| 久久久久久综合一区中文字幕 | 久久国产精品-国产精品| 精品无码久久久久久久久久| 国产精自产拍久久久久久蜜|