CF19E Fairy

题意：

删掉若干条边使原图成为二分图的方案数。

题解：

考虑DFS树。

答案为所有奇环的交减掉偶环的并。

这里的环指的是由一条非树边和若干条树边组成的环。

如果一个奇环和偶环在树边上有交集，那么删掉交集部分后会形成新的奇环，而删掉奇环的非树边则会破坏奇环。

首先考虑只有一个奇环的情况。

首先奇环的非树边显然是可以删掉的，删掉后破坏了奇环。

其次，奇环的树边，只要不被另一个偶环覆盖，那么也可以删（如果被覆盖了，删掉后会拼成一个新的奇环）

考虑由多个奇环的情况。

答案是所有奇环的公共部分。

直接在树上打标记即可。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 10000;

struct State
{
    int_t depth;
    int_t vertex;
    bool operator<(const State &x) const
    {
        return depth < x.depth;
    }
    State(int_t vertex = -1, int_t depth = 0)
    {
        this->depth = depth;
        this->vertex = vertex;
    }
} seq[20][LARGE * 3 + 1];
struct Edge
{
    int_t to;
    int_t id;
    int_t from = -1;
};
int_t count = 0;
int_t first[LARGE + 1];
int_t depth[LARGE + 1];
std::vector<Edge> graph[LARGE + 1];
std::vector<Edge> nonetree[LARGE + 1];
std::vector<int_t> stage[LARGE + 1];
Edge inEdge[LARGE + 1];
bool visited[LARGE + 1];
int_t mark[LARGE + 1];
int_t parent[LARGE + 1];
int_t n, m;
void DFS0(int_t vertex, int_t from = -1, int_t depth = 1)
{
    if (visited[vertex])
        return;
    // cout << "visiting " << vertex << endl;
    ::parent[vertex] = from;
    stage[depth].push_back(vertex);
    ::depth[vertex] = depth;
    visited[vertex] = true;
    seq[0][++count] = State(vertex, depth);
    if (first[vertex] == 0)
        first[vertex] = count;
    for (auto &edge : graph[vertex])
    {
        if (visited[edge.to] && edge.to != from && ::depth[edge.to] > ::depth[vertex])
        {
            nonetree[vertex].push_back(edge);
        }
        else if (visited[edge.to] == false)
        {
            inEdge[edge.to] = edge;
            DFS0(edge.to, vertex, depth + 1);
            seq[0][++count] = State(vertex, depth);
            if (first[vertex] == 0)
                first[vertex] = count;
        }
    }
}
void init()
{
    for (int_t i = 1; (1 << i) <= count; i++)
    {
        for (int_t j = 1; j + (1 << i) - 1 <= count; j++)
        {
            seq[i][j] = std::min(seq[i - 1][j], seq[i - 1][j + (1 << (i - 1))]);
        }
    }
}
int_t getLCA(int_t v1, int_t v2)
{
    v1 = first[v1];
    v2 = first[v2];
    if (v1 > v2)
        std::swap(v1, v2);
    int_t i = std::log2(v2 - v1 + 1);
    return std::min(seq[i][v1], seq[i][v2 - (1 << i) + 1]).vertex;
}
int main()
{
    cin >> n >> m;
    for (int_t i = 1; i <= m; i++)
    {
        int_t from, to;
        cin >> from >> to;
        graph[from].push_back(Edge{to, i});
        graph[to].push_back(Edge{from, i});
    }
    for (int_t i = 1; i <= n; i++)
    {
        if (visited[i] == false)
        {
            DFS0(i);
        }
    }
    init();
    int_t count = 0;
    std::vector<Edge> evens;
    for (int_t i = 1; i <= n; i++)
    {
        for (auto &edge : nonetree[i])
        {
            int_t dis = depth[i] + depth[edge.to] - 2 * depth[getLCA(edge.to, i)] + 1;
            int_t mark;
            //偶环
            if (dis % 2 == 0)
            {
                mark = -1;
            }
            else
            { //奇环
                mark = 1;
                count++;
                evens.push_back(Edge{i, edge.id, edge.to});
            }
            ::mark[i] += mark;
            ::mark[edge.to] += mark;
            ::mark[getLCA(edge.to, i)] -= 2 * mark;
        }
    }
    for (int_t i = n; i >= 2; i--)
    {
        for (int_t vtx : stage[i])
        {
            mark[parent[vtx]] += mark[vtx];
        }
    }
    std::vector<int_t> result;
    if (count == 0)
    {
        for (int_t i = 1; i <= m; i++)
        {
            result.push_back(i);
        }
    }
    else if (count == 1)
    {
        int_t v1 = evens[0].from;
        int_t v2 = evens[0].to;
        int_t lca = getLCA(v1, v2);
        result.push_back(evens[0].id);
        while (v1 != lca)
        {
            if (mark[v1] == 1)
            {
                result.push_back(inEdge[v1].id);
            }
            v1 = parent[v1];
        }
        while (v2 != lca)
        {
            if (mark[v2] == 1)
            {
                result.push_back(inEdge[v2].id);
            }
            v2 = parent[v2];
        }
    }
    else if (count > 1)
    {
        for (int_t i = 1; i <= n; i++)
        {
            if (parent[i] != -1 && mark[i] == evens.size())
            {
                result.push_back(inEdge[i].id);
            }
        }
    }
    std::sort(result.begin(), result.end());
    cout << result.size() << endl;
    for (int_t x : result)
        cout << x << " ";
    cout << endl;
    return 0;
}