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

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            99久久久精品| 久久精品国产亚洲AV香蕉| 2021少妇久久久久久久久久| 久久天天躁狠狠躁夜夜网站| 久久久九九有精品国产| 久久精品国产亚洲麻豆| 婷婷久久综合九色综合绿巨人| 久久中文字幕人妻丝袜| 伊人久久大香线焦综合四虎| 伊人久久一区二区三区无码| 久久精品国产半推半就| 午夜精品久久久久久影视777| avtt天堂网久久精品| 久久久久香蕉视频| 97精品国产91久久久久久| 香蕉99久久国产综合精品宅男自| 久久久久久九九99精品| 亚洲欧美另类日本久久国产真实乱对白| 日产精品99久久久久久| 婷婷久久综合九色综合绿巨人| 久久精品人人做人人爽97| 久久久久亚洲AV无码专区首JN| 亚洲国产精品热久久| 久久久久人妻一区精品色 | 国产—久久香蕉国产线看观看| 亚洲国产成人久久综合野外 | 久久午夜无码鲁丝片午夜精品| 久久精品人人做人人爽97| 国内精品久久久久影院薰衣草 | 国产高潮国产高潮久久久| 中文字幕精品久久| 日韩电影久久久被窝网| 国产激情久久久久影院小草| 久久亚洲春色中文字幕久久久| 亚洲人成网亚洲欧洲无码久久| 久久青青色综合| 97久久婷婷五月综合色d啪蜜芽| 久久九九兔免费精品6| 一本一道久久综合狠狠老| 亚洲中文字幕无码久久精品1 | 久久精品国产亚洲AV麻豆网站|