Editorial for Bedao Mini Contest 11 - TREECOLORING
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Giả sử ta bắt đầu với một node bất kỳ với màu đỏ, ta có thể tham lam nếu như cạnh nối với node đó là lẻ thì đầu mút còn lại sẽ tô màu đen, ngược lại sẽ là màu đỏ. Thực hiện như vậy đến khi ~DFS~ toàn bộ cây.
Độ phức tạp: ~O(n)~
Code mẫu
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; using ii = pair<ll, ll>; #define fastIO ios::sync_with_stdio(0); cin.tie(0); #define pb push_back #define fi first #define se second #define numBit(x) (__builtin_popcountll(1ll * (x))) #define getBit(x, i) ((x) >> (i) & 1) #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() template<class X, class Y> bool minimize(X &x, const Y &y) { X eps = 1e-9; if (x > y + eps) { x = y; return true; } else return false; } template<class X, class Y> bool maximize(X &x, const Y &y) { X eps = 1e-9; if (x + eps < y) { x = y; return true; } else return false; } const int N = 1e5 + 7; int n; bool color[N]; vector<ii> adj[N]; void dfs(int u, int par, bool odd) { if (!odd) color[u] = 1; for (auto [v, w]: adj[u]) if (v != par) { dfs(v, u, (w & 1) ^ odd); } } int main() { #ifndef ONLINE_JUDGE freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); #endif cin >> n; for (int i = 1, u, v, w; i <= n; i++) { cin >> u >> v >> w; adj[u].pb(ii(v, w)); adj[v].pb(ii(u, w)); } dfs(1, 1, 0); for (int i = 1; i <= n; i++) cout << color[i] << ' '; }
Comments