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

            Ural 1080 Map Colouring

            1080. Map Colouring

            Time Limit: 1.0 second
            Memory Limit: 16 MB
            We consider a geographical map with N countries numbered from 1 to N (0 < N < 99). For every country we know the numbers of other countries which are connected with its border. From every country we can reach to any other one, eventually crossing some borders. Write a program which determines whether it is possible to colour the map only in two colours — red and blue in such a way that if two countries are connected their colours are different. The colour of the first country is red. Your program must output one possible colouring for the other countries, or show, that such colouring is impossible.

            Input

            On the first line is written the number N. On the following N lines, the i-th line contains the countries to which the i-th country is connected. Every integer on this line is bigger than i, except the last one which is 0 and marks that no more countries are listed for country i. If a line contains 0, that means that the i-th country is not connected to any other country, which number is larger than i.

            Output

            The output contains exactly one line. If the colouring is possible, this line must contain a list of zeros and ones, without any separators between them. The i-th digit in this sequence is the colour of the i-th country. 0 corresponds to red colour, and one — to blue colour. If a colouring is not possible, output the integer −1.

            Sample

            input output
            3
                                    2 0
                                    3 0
                                    0
                                    
            010
                                    

            DFS:或BFS,或者并查集(不會用)
            這里用的DFS,用一個標記數組,沒進入一個聯通分圖后,標記為0(表示一種顏色)與它相連的標記為1(另一種顏色),
            然后與1相連的在標記為0。 這里的標記都是對沒有標記過的進行的,如果是標記過的,就要檢查他們的標記是否相同
            如果相同則說明,他們同色。
            //ural 1080
            #include<iostream>
            using namespace std;

            const int MAX=100;
            bool adj[MAX][MAX];
            int flg[MAX];
            int n;
            bool isPossible=true;

            void input()
            {
                 cin
            >>n;
                 
            int temp;
                 
            for(int i=1; i<=n; i++)
                 {
                         
            while(cin>>temp,temp!=0)
                         {
                                                 adj[i][temp]
            =adj[temp][i]=true;
                         }
                 }
            }

            void dfs(int i)
            {
                 
            if(isPossible==false)return ;
                 
            if(flg[i]==-1)flg[i]=0;
                 
            for(int j=1; j<=n; j++)
                 {
                         
            if(adj[i][j])
                         {
                                      
            if(flg[j]==-1){ flg[j]=flg[i]==0? 1:0;  dfs(j); } 
                                      
            else if(flg[j]==flg[i])isPossible=false;
                                      
                         }
                 }
                 
            }

            int main()
            {
                memset(adj,
            0,sizeof adj);
                
                input();
                
            for(int i=1; i<=n; i++
                       flg[i]
            =-1;  
                
                flg[
            1]=0;
                
            for(int i=1; i<=n; i++)
                        dfs(i);
                
                
            if(isPossible==false)cout<<-1<<endl;
                
            else { 
                     
            for(int k=1; k<=n; k++)
                         cout
            <<flg[k];
                     cout
            <<endl;
                       }
                         
                
                system(
            "pause");
                
            return 0;
            }

            posted on 2010-07-31 17:17 田兵 閱讀(288) 評論(0)  編輯 收藏 引用 所屬分類: URAL

            <2010年7月>
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            導航

            統計

            常用鏈接

            留言簿(2)

            隨筆分類(65)

            隨筆檔案(65)

            文章檔案(2)

            ACM

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            久久91精品久久91综合| 久久久久久久综合日本亚洲 | 亚洲嫩草影院久久精品| 久久99精品久久久久久不卡| 97超级碰碰碰碰久久久久| 日本久久中文字幕| 亚洲精品无码久久久影院相关影片| 性欧美丰满熟妇XXXX性久久久 | 久久精品国产亚洲av麻豆色欲| 精品久久久久中文字幕日本| 国内精品久久久久久久亚洲| 合区精品久久久中文字幕一区| 97久久国产综合精品女不卡 | 狠狠久久综合| 久久丫精品国产亚洲av| 久久久无码精品亚洲日韩软件| 波多野结衣久久一区二区| 久久亚洲高清观看| 伊人久久久AV老熟妇色| 久久婷婷五月综合色99啪ak| 亚洲精品高清国产一线久久| 国产亚洲色婷婷久久99精品91| 亚洲国产精品久久久天堂| 香港aa三级久久三级老师2021国产三级精品三级在 | 久久久精品国产sm调教网站 | 无码日韩人妻精品久久蜜桃 | 国产综合精品久久亚洲| 久久超碰97人人做人人爱| 久久这里有精品| 久久久WWW成人免费精品| 久久久久国产精品| 久久精品亚洲中文字幕无码麻豆| 香蕉99久久国产综合精品宅男自 | 久久天天躁狠狠躁夜夜网站 | 国产午夜精品理论片久久| 久久精品国产亚洲沈樵| 久久久国产精华液| 亚洲人成精品久久久久| 久久精品中文字幕一区 | 国产成人香蕉久久久久| 日韩欧美亚洲综合久久影院d3|