Editorial for Bedao Mini Contest 12 - COLORCYC
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:
Nếu ~m = 0~, thì số màu ít nhất cần sử dụng là ~0~.
Nếu đồ thị không có chu trình, thì số màu ít nhất cần sử dụng là ~1~.
Nếu đồ thị có chu trình, thì ta thấy cần sử dụng nhiều hơn ~1~ màu, ta có cách tô sử dụng ~2~ màu như sau: Xét cung ~(u, v)~ - Nếu ~u < v~ thì tô màu số hiệu ~1~. - Nếu ~u > v~ thì tô màu số hiệu ~2~.
Ở hai trường hợp đầu tiên, ta dễ dàng thấy nó đúng. Còn ở trường hợp thứ ba ta thấy rằng: Xét từng chu trình trong đồ thị có dạng: ~x_1, x_2, \dots, x_k, x_{k+1} = x_1~, luôn tồn tại vị trí ~h~ có ~x_{h-1} < x_h > x_{h+1}~ thì chu trình đang xét sẽ được tô hai màu. Màu ~1~ ở cung ~(x_{h-1}, x_h)~ và màu ~2~ ở cung ~(x_{h}, x_{h + 1})~.
Code mẫu
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 7; vector <int> adj[MAXN]; pair <int, int> e[MAXN]; int n, m, d[MAXN]; bool cycle = 0; void DFS(int u) { if (cycle) return; d[u] = 1; for (auto v: adj[u]) if (!d[v]) DFS(v); else if (d[v] == 1) cycle = 1; d[u] = 2; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; if (m == 0) return cout << 0, 0; for (int i = 1; i <= m; ++i) { cin >> e[i].first >> e[i].second; adj[e[i].first].push_back(e[i].second); } for (int i = 1; i <= n; ++i) if (!d[i]) DFS(i); cout << cycle + 1 << '\n'; for (int i = 1; i <= m; ++i) if (e[i].first < e[i].second) cout << "1\n"; else cout << 1 + cycle << '\n'; return 0; }
Comments