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

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            99精品久久精品一区二区| 99国内精品久久久久久久| 无码精品久久一区二区三区 | 九九精品99久久久香蕉| 丁香五月网久久综合| 精品国产青草久久久久福利| 最新久久免费视频| 人人狠狠综合久久亚洲88| 久久受www免费人成_看片中文| 色妞色综合久久夜夜| 国产精品无码久久四虎| 久久久无码精品亚洲日韩蜜臀浪潮 | 久久久久亚洲精品天堂久久久久久| 国产毛片欧美毛片久久久| 国产精品国色综合久久| 亚洲精品乱码久久久久久不卡| 四虎影视久久久免费观看| 亚洲精品无码久久久久久| 99久久做夜夜爱天天做精品| 99久久精品免费| 伊人久久大香线蕉综合Av| 久久久久亚洲爆乳少妇无 | 无码久久精品国产亚洲Av影片 | 久久天天躁狠狠躁夜夜2020一| 精品熟女少妇aⅴ免费久久| 综合网日日天干夜夜久久| 久久综合一区二区无码| 99久久成人国产精品免费| 久久综合国产乱子伦精品免费| 亚洲午夜无码久久久久| 亚洲精品无码久久久久| 久久强奷乱码老熟女网站| 欧美日韩中文字幕久久久不卡 | 久久精品一本到99热免费| 久久午夜夜伦鲁鲁片免费无码影视 | 国产亚洲美女精品久久久2020| 日韩精品无码久久一区二区三| 久久久精品久久久久久| 国产精品99久久久久久猫咪| 欧美伊香蕉久久综合类网站| 国产无套内射久久久国产|