URAL 1080. Map Coloring

Author: 2015-08-23

ACM

, ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1080

1080. Map Coloring

Time limit: 1.0 second
Memory limit: 64 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 color the map only in two colors — red and blue in such a way that if two countries are connected their colors are different. The color of the first country is red. Your program must output one possible coloring for the other countries, or show, that such coloring 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 coloring 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 color of the i-th country. 0 corresponds to red color, and one — to blue color. If a coloring is not possible, output the integer −1.

Sample

input output 
3
2 0
3 0
0

010
Problem Author: Emil Kelevedzhiev
Problem Source: Winter Mathematical Festival Varna ‘2001 Informatics Tournament

2. 思路

给出地图上若干的国家和它们的接壤关系，用两种颜色给各个国家上色，要求相邻国家使用不同的颜色，如可行，求上色方案。

BFS，对每个国家c，遍历其邻国：如该邻国没有上色，则填充与国家c不同的颜色，入队；如该邻国已上色，且该邻国颜色与国家c相同，则无解。

3.代码

#include <stdio.h>

#define MAX_COUNTRY_NUM 99
#define UNCONNECTED 0
#define CONNECTED 1
#define STAT_RED 0
#define STAT_BLUE 1
#define STAT_UNVISITED 2

typedef char Map[MAX_COUNTRY_NUM + 1][MAX_COUNTRY_NUM + 1];


void solveE1d();
int inputMap(Map map);
void initMap(Map map, int countryNum);
int colorMap(Map map, int countryNum, char stat[]);
int changeColor(int color);
void printStat(char stat[], int countryNum);
void printMap(Map map, int countryNum);

int main(int argc, const char * argv[]) {
    solveE1d();
    return 0;
}

Map map;
char countryStat[MAX_COUNTRY_NUM + 1];
void solveE1d() {
    int countryNum, result;

    countryNum = inputMap(map);
    // printMap(map, countryNum);
    result = colorMap(map, countryNum, countryStat);
    if (result == -1) {
        printf("-1\n");
    } else {
        printStat(countryStat, countryNum);
    }
}

int inputMap(Map map) {
    int countryNum, i, connected;
    
    scanf("%d", &countryNum);
    initMap(map, countryNum);
    
    for (i = 1; i <= countryNum;) {
        scanf("%d", &connected);
        if (connected != 0) {
            map[i][connected] = CONNECTED;
            map[connected][i] = CONNECTED;
        } else {
            ++i;
        }
    }
    
    return countryNum;
}

void initMap(Map map, int countryNum) {
    int i, j;
    
    for (i = 1; i <= countryNum; ++i) {
        for (j = 1; j <= countryNum; ++j) {
            map[i][j] = UNCONNECTED;
        }
    }
}

char queue[MAX_COUNTRY_NUM + 1];
int colorMap(Map map, int countryNum, char countryStat[]) {
    int i, front = 0, rear = 0, currCountry, currColor, nextColor,
        isolatedCountry = 1;
    
    for (i = 1; i <= countryNum; ++i) {
        countryStat[i] = STAT_UNVISITED;
    }
    
    queue[rear++] = 1;
    countryStat[1] = STAT_RED;
    
    while (front < rear) {
        currCountry = queue[front++];
        currColor = countryStat[currCountry];
        nextColor = changeColor(currColor);
        for (i = 1; i <= countryNum; ++i) {
            if (map[currCountry][i] == CONNECTED) {
                if (countryStat[i] == STAT_UNVISITED) {
                    queue[rear++] = i;
                    countryStat[i] = nextColor;
                } else if (countryStat[i] == currColor) {
                    return -1;
                }
            }
        }
        
        if (front == rear) {
            for (i = isolatedCountry; i <= countryNum; ++i) {
                if (countryStat[i] == STAT_UNVISITED) {
                    isolatedCountry = i;
                    queue[rear++] = i;
                    countryStat[i] = STAT_RED;
                    break;
                }
            }
        }
    }
    
    return 1;
}

int changeColor(int color) {
    if (color == STAT_RED) {
        return STAT_BLUE;
    } else {
        return STAT_RED;
    }
}

void printStat(char stat[], int countryNum) {
    int i;
    
    for (i = 1; i <= countryNum; ++i) {
        printf("%d", stat[i]);
    }
    printf("\n");
    
}

void printMap(Map map, int countryNum) {
    int i, j;
    
    for (i = 1; i <= countryNum; ++i) {
        for (j = 1; j <= countryNum; ++j) {
            printf("%d ", map[i][j]);
        }
        printf("\n");
    }
}