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 田兵 阅读(156) 评论(0)  编辑 收藏 引用 所属分类: URAL


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年6月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜