noi.ac 165染色

一场由于忘记清空数组而引发的血案。

下次我还是开对象处理多组数据吧

首先判无解，如果存在任意一个点的度数小于2或者为奇数则无解。

其他情况，让k成为最大的使得$2^k|gcd(degs)$的k，其中degs是全体点度数的集合。

然后对原图的边进行交错染色，然后这就确定了第k-1位的取值。

黑色的边的颜色的第k-1位设定为1，白色的边设定为0.

然后把两种颜色的边拿出来，递归下去按照相同的方法确定第k-2位。

# 不要忘记在判无解后清空数组！！！

#include <assert.h>
#include <algorithm>
#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>
using int_t = long long int;
using set_t = std::unordered_set<int_t>;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 2e5;

struct Edge {
    int_t to, id, from;
} edges[LARGE + 1];

std::vector<Edge> graph[LARGE + 1];
int_t color[LARGE + 1];
int_t degree[LARGE + 1];
bool visited[LARGE + 1];
int_t n, m;
//从点vtx出发，这一位的掩码为mask，上一条边的颜色为lastcolor
void DFS(int_t vtx, int_t lastcolor, int_t mask) {
    for (int_t i = graph[vtx].size() - 1; i >= 0 && i < graph[vtx].size();
         i--) {
        if (visited[graph[vtx][i].id] == false) {
            color[graph[vtx][i].id] |= (lastcolor ^ mask);
            visited[graph[vtx][i].id] = true;
            int_t to = graph[vtx][i].to;
            graph[vtx].pop_back();
            DFS(to, lastcolor ^ mask, mask);
        } else {
            graph[vtx].pop_back();
        }
    }
}
//当前对第bit位进行染色
void process(int_t* left, int_t* right, int_t bit) {
    if (bit == -1) return;
    if (left > right) return;
    for (auto ptr = left; ptr <= right; ptr++) {
        const auto& edge = ::edges[*ptr];
        graph[edge.from].push_back(Edge{edge.to, edge.id});
        graph[edge.to].push_back(Edge{edge.from, edge.id});
    }
    for (auto ptr = left; ptr <= right; ptr++) {
        const auto& edge = ::edges[*ptr];
        if (visited[edge.id] == false) DFS(edge.from, 0, 1 << bit);
    }
    static int_t zeros[LARGE + 1], ones[LARGE + 1];
    zeros[0] = ones[0] = 0;
    for (auto ptr = left; ptr <= right; ptr++) {
        const auto& edge = ::edges[*ptr];
        graph[edge.from].clear();
        graph[edge.to].clear();
        if (color[edge.id] & (1 << bit))
            ones[++ones[0]] = *ptr;
        else
            zeros[++zeros[0]] = *ptr;
        visited[edge.id] = false;
    }

    std::copy(zeros + 1, zeros + 1 + zeros[0], left);
    auto last = left + zeros[0];
    std::copy(ones + 1, ones + 1 + ones[0], last);
    assert(last - left == right - last + 1);
    process(left, last - 1, bit - 1);
    process(last, right, bit - 1);
}
int_t gcd(int_t a, int_t b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
int main() {
    while (true) {
        scanf("%lld%lld", &n, &m);
        if (n == 0) break;
        for (int_t i = 1; i <= m; i++) {
            int_t from, to;
            scanf("%lld%lld", &from, &to);
            degree[from]++, degree[to]++;
            edges[i].to = to;
            edges[i].from = from;
            edges[i].id = i;
        }
        int_t ors = 0;
        for (int_t i = 1; i <= n; i++) ors = gcd(ors, degree[i]);
        int_t k = 0;
        while (ors % 2 == 0) {
            k++;
            ors /= 2;
        }
        for (int_t i = 1; i <= n; i++)
            if ((degree[i] & 1) || degree[i] < 2) k = -1;
        if (m & 1) k = -1;
        if (k == -1) {
            cout << -1 << endl;
            std::fill(degree + 1, degree + 1 + n, 0);
            std::fill(color + 1, color + 1 + m, 0);
            continue;
        }
        static int_t edges[LARGE + 1];
        for (int_t i = 1; i <= m; i++) edges[i] = i;
        process(edges + 1, edges + m, k - 1);
        printf("%lld\n", k);
        for (int_t i = 1; i <= m; i++) printf("%lld ", color[i] + 1);
        std::fill(degree + 1, degree + 1 + n, 0);
        std::fill(color + 1, color + 1 + m, 0);
        printf("\n");
    }
    return 0;
}