用c++解决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.

以下是使用C++解决1080. Map Coloring问题的代码：

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100;
vector<int> graph[MAXN]; // 存储图

int color[MAXN]; // 存储每个国家的颜色

bool dfs(int u, int c) {
    color[u] = c; // 标记当前国家的颜色
    for (int i = 0; i < graph[u].size(); i++) {
        int v = graph[u][i];
        if (color[v] == c) { // 如果相邻国家颜色相同，返回false
            return false;
        } else if (color[v] == 0 && !dfs(v, -c)) { // 如果相邻国家未被标记，继续搜索
            return false;
        }
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int v;
        while (cin >> v && v != 0) {
            graph[i].push_back(v);
            graph[v].push_back(i);
        }
    }
    if (!dfs(1, 1)) { // 从第一个国家开始DFS，如果无法着色，输出-1
        cout << "-1" << endl;
    } else {
        for (int i = 1; i <= n; i++) {
            cout << (color[i] == 1 ? "0" : "1"); // 输出每个国家的颜色
        }
        cout << endl;
    }
    return 0;
}

首先读入每个国家相邻的国家，构建图。然后从第一个国家开始DFS，对每个国家进行着色，如果发现相邻国家颜色相同，则返回false，表示无法着色。如果整张地图都被着色，则输出每个国家的颜色。