加载中…
个人资料
Max0857
Max0857
  • 博客等级:
  • 博客积分:0
  • 博客访问:41,734
  • 关注人气:15
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

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

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

noip

oi

ural

算法

搜索

图论

it

分类: Ural译题及题解
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.

一幅地图有N个国家,编号为1到N(0<99)。每个国家都可能与其他的一些国家接壤。你的任务是编一个程序来确定是否可以只用两种颜色为地图着色。两个接壤的国家必须用不同的颜色--红色和蓝色来表示,且规定第一个国家的颜色是红色。你的程序必须为所有国家输出一种可能的着色方法,或输出不能着色。

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.

在第一行为编号N。在以下的N行中,第i行包含与第i个国家相接壤的国家。且每行中的每个数都大于1,每行最后以"0"结尾。如果一行只有一个0,就意味着这个国家不与任何一个国家接壤。

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.

输出包括只有一行。如果能够着色,这行只能包括一串0和1,中间没有任何空格。在这一行中,第i个数表示第i个国家的颜色,0相当于红色,1相当于蓝色,如果无法着色,则输出-1。

Sample Input

3
2 0
3 0
0

Sample Output

010
【分析】
直接深搜!
【参考代码】
#include<stdio.h>
#include<string.h>
int c[10001];
int adj[1001][1001];
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++)
 {
  if(adj[v][i])
  {
   adj[v][i]=false;
   adj[i][v]=false;
   color(i,1-x);
  }
 }
}
int main()
{
 memset(c,-1,sizeof(c));
 memset(adj,0,sizeof(adj));
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
  while(1)
  {
   int x;
   scanf("%d",&x);
   if(x==0) break;
   adj[i][x]=true;
   adj[x][i]=true;
  }
 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

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

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

      

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

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有