• <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 閱讀(879) 評論(0)  編輯 收藏 引用 所屬分類: graph

            <2010年10月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            国产毛片欧美毛片久久久| 伊人久久大香线蕉无码麻豆 | 伊人热人久久中文字幕| 99久久国产免费福利| 久久精品无码一区二区三区日韩 | 久久夜色精品国产欧美乱| 久久这里只有精品首页| 国产成人无码精品久久久性色| 久久香综合精品久久伊人| 国产精品久久久久乳精品爆 | 久久91精品国产91久久户| 一本久道久久综合狠狠躁AV| 亚洲午夜久久久影院| 久久99精品久久久久久秒播| 777久久精品一区二区三区无码| 欧美久久久久久精选9999| 青青久久精品国产免费看| 国产美女久久精品香蕉69| 久久人与动人物a级毛片| 久久国产香蕉视频| 久久久久久久久无码精品亚洲日韩| 伊人久久精品无码av一区| 久久久久国产视频电影| 久久久久国产精品熟女影院| 影音先锋女人AV鲁色资源网久久| 久久国产热这里只有精品| 欧美久久精品一级c片片| 久久精品人人做人人爽97| 中文字幕无码免费久久| 女人高潮久久久叫人喷水| 亚洲国产成人久久一区久久| 国内精品久久久久久麻豆| 久久99国产精品久久99| 人人狠狠综合久久亚洲婷婷| av午夜福利一片免费看久久| 久久国产乱子伦精品免费强| 国产精品一久久香蕉产线看| 精品久久久久久无码国产| 色综合久久综合网观看| 久久er国产精品免费观看8| 久久久久久久综合综合狠狠|