Hướng dẫn giải của Bedao Mini Contest 12 - COLORCYC


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

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;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.