# 加载中...

Max0857
• 博客等级：
• 博客积分：0
• 博客访问：41,734
• 关注人气：15
• 获赠金笔：0支
• 赠出金笔：0支
• 荣誉徽章：

## 【Ural 1080】Map Colouring (地图着色)

(2009-06-05 19:55:37)

### it

Map Colouring 地图着色

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 lines 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 coresponds to red colour, and one - to blue colour. If a colouring is not possible, output the integer -1.

3
2 0
3 0
0

## Sample Output

010
【分析】

【参考代码】
#include<stdio.h>
#include<string.h>
int c[10001];
int n;
bool tiao=false;
void color(int v,int x)
{
int i;
if(tiao) return;
if(c[v]>-1)
{
if(c[v]==x) return;
else
{
printf("-1\n");
tiao=true;
return;
}
}
c[v]=x;
for(i=1;i<=n;i++)
{
{
color(i,1-x);
}
}
}
int main()
{
memset(c,-1,sizeof(c));
scanf("%d",&n);
for(int i=1;i<=n;i++)
while(1)
{
int x;
scanf("%d",&x);
if(x==0) break;
}
for(int i=1;i<=n;i++)
if(c[i]==-1) color(i,0);
if(tiao) return 0;
for(int i=1;i<=n;i++)
printf("%d",c[i]);
printf("\n");
return 0;
}

0

• 评论加载中，请稍候...

发评论

以上网友发言只代表其个人观点，不代表新浪网的观点或立场。

新浪BLOG意见反馈留言板　电话：4000520066 提示音后按1键（按当地市话标准计费）　欢迎批评指正

新浪公司 版权所有