题目：有k行，每行包含第i个点相邻的点。现有0/1两种颜色，相邻的颜色必须不一样，如果能进行涂色，输出每个点的颜色，如果不能进行涂色，则输出-1。
解析：
1. BFS
2. 我没用那么高级的方法，就只用vector迭代涂色。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include<iostream> #include<vector> #include<map> #include<set> using namespace std; vector<vector<int>>connection; vector<pair<int, int>>color; set<int>finish; int coloring(vector<int> &singleConnection, int colorNow, int point) { set<int>::iterator ptr; ptr = finish.find(point); finish.erase(ptr); int colorTemp; for (int i = 0; i < singleConnection.size(); i++) { colorTemp = color[singleConnection[i]].second; if (colorTemp == -1) { color[singleConnection[i]].second = 1 - colorNow; int error = coloring(connection[singleConnection[i]], 1 - colorNow, singleConnection[i]); if (error == -1)return -1; } else if(colorNow == colorTemp) { return -1; } } return 0; } int main() { int n, temp; cin >> n; for (int i = 0; i < n; i++) { vector<int>connectTemp; connection.push_back(connectTemp); } for (int i = 0; i < n; i++) { color.push_back(make_pair(i, -1)); finish.insert(i); while (1) { cin >> temp; if (temp != 0) { connection[i].push_back(temp - 1); connection[temp - 1].push_back(i); } else break; } } while (!finish.empty()) { color[*finish.begin()].second = 0; int error = coloring(connection[*finish.begin()], 0, *finish.begin()); if(error == -1) { cout << -1 << endl; return 0; } } for (auto i : color)cout << i.second; } |
浙公网安备 33010902002953号