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

            poj2513 Colored Sticks 圖的連通性判斷+歐拉圖判斷。圖里的問題注意首先判斷連通性

            題意:
            給出一堆木棍和兩端的顏色,問能否將木棍連成一排,接頭處兩木棍的顏色相同

            解法:
            這題我開始大意了,直接按歐拉圖的條件(應該說是否存在一個歐拉跡)判斷奇數度的節點個數是否為0或2,沒有考慮判斷圖的連通性
            這里再次提醒自己圖里的問題注意首先判斷連通性

            代碼:
             1import java.io.*;
             2import java.util.*;
             3public class Main {
             4
             5    /**
             6     * @param args
             7     */

             8    static int pre[]=new int[510000];
             9    static int find(int pos)
            10    {
            11      if(pre[pos]==pos) return pos;
            12      else
            13      {
            14          pre[pos]=find(pre[pos]);
            15          return pre[pos];
            16      }

            17    }

            18    static void union(int t1,int t2)
            19    {
            20        pre[find(t1)]=find(t2);
            21    }

            22    public static void main(String[] args) throws IOException{
            23        StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
            24        HashMap<String,Integer> count=new HashMap<String,Integer>();
            25        HashMap<String,Integer> id=new HashMap<String,Integer>();
            26        int c=0;
            27        while(in.nextToken()!=in.TT_EOF)
            28        {
            29            String t1=in.sval;
            30            if(count.containsKey(in.sval))
            31                count.put(in.sval, count.get(in.sval)+1);
            32            else
            33                {
            34                  pre[c]=c; 
            35                  id.put(in.sval, c++);
            36                   
            37                   count.put(in.sval, 1);
            38                }

            39            in.nextToken();
            40            if(count.containsKey(in.sval))
            41                count.put(in.sval, count.get(in.sval)+1);
            42            else
            43            {
            44               pre[c]=c;
            45               id.put(in.sval, c++);
            46               count.put(in.sval, 1);
            47            }

            48            union(id.get(t1),id.get(in.sval));
            49        }

            50        int total=1;
            51        for(int i=1;i<c;i++)
            52            if(find(i)!=find(i-1))
            53                total++;
            54        if(total>1)
            55        {
            56            System.out.println("Impossible");
            57            return;
            58        }

            59        total=0;
            60        for(int p:count.values())
            61            if(p%2==1) total++;
            62        if(total!=0&&total!=2
            63            System.out.println("Impossible");
            64        else 
            65            System.out.println("Possible");
            66
            67    }

            68
            69}

            70

            posted on 2011-01-12 08:53 yzhw 閱讀(878) 評論(0)  編輯 收藏 引用 所屬分類: graph

            <2010年11月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            777午夜精品久久av蜜臀| 国产 亚洲 欧美 另类 久久| 日韩电影久久久被窝网| 蜜桃麻豆www久久国产精品| 四虎久久影院| 国产精品美女久久久久| 国内精品久久久久国产盗摄| 久久亚洲电影| 97久久精品午夜一区二区| 色成年激情久久综合| 大香伊人久久精品一区二区| 久久中文字幕一区二区| 久久妇女高潮几次MBA| 999久久久无码国产精品| 中文成人无码精品久久久不卡| 精品久久久久久无码专区不卡| 久久久精品久久久久久 | 亚洲精品视频久久久| 99久久超碰中文字幕伊人| 亚洲七七久久精品中文国产| 中文精品久久久久国产网址| 少妇人妻88久久中文字幕| 久久毛片免费看一区二区三区| 999久久久免费精品国产| 亚洲国产精品18久久久久久| 一级做a爰片久久毛片毛片| 久久久久久极精品久久久| 人人狠狠综合久久亚洲88| 久久亚洲精精品中文字幕| 久久久无码精品亚洲日韩京东传媒| 国产成人无码精品久久久久免费 | 国产亚洲精久久久久久无码77777| 久久97精品久久久久久久不卡| 午夜欧美精品久久久久久久| 久久综合久久综合亚洲| 天天影视色香欲综合久久| 久久婷婷五月综合成人D啪| 久久久久久噜噜精品免费直播| 国产99久久九九精品无码| 日本免费一区二区久久人人澡| 99久久精品费精品国产|