building_teams_1668.cpp (737B)
1 #include <iostream> 2 #include <vector> 3 4 bool visit(size_t i, int c, const std::vector<std::vector<size_t>>& a, 5 std::vector<int>& t) { 6 if (t[i] != 0) return true; 7 t[i] = c; 8 for (auto j : a[i]) 9 if (t[j] == c) 10 return false; 11 else if (!visit(j, 3-c, a, t)) return false; 12 return true; 13 } 14 15 int main() { 16 size_t n, m; 17 std::cin >> n >> m; 18 std::vector<std::vector<size_t>> a(n); 19 for (size_t i = 0; i < m; i++) { 20 size_t x, y; 21 std::cin >> x >> y; 22 a[x-1].push_back(y-1); 23 a[y-1].push_back(x-1); 24 } 25 26 std::vector<int> t(n); 27 for (size_t i = 0; i < n; i++) { 28 if (t[i] == 0) { 29 if (!visit(i, 1, a, t)) { 30 std::cout << "IMPOSSIBLE\n"; 31 return 0; 32 } 33 } 34 } 35 for (auto x : t) std::cout << x << " "; 36 std::cout << "\n"; 37 }