「Solution」Fairy

十年前的紫题?

$\mathbb{Fairy}$

$\mathcal{Link}$

link

$\mathcal{Sol}$

这道题充分说明我二分图没整抻抖。

考察了一个基本的性质，如果这张图是二分图，那么图中一定不含奇环。
然而我再知道性质的情况下不会做。。。

再重新理一遍思路。

$\mathcal{Part \ 1 \ Dfs}$

首先染色，根据染色规律可以知道，如果一个点与它相邻的某个点染上了同样的颜色，则它存在于奇环上。
于是可以树上差分维护。
注意判断返租边应该是dep[v] < dep[u] - 1。
顺便记录奇环的个数。

$\mathcal{Part \ 2 \ Check}$

• 如果有偶环，偶环上的所有边都不能删
• 如果没有奇环，所有边都可以删
• 如果有一个奇环，这个奇环上的所有边都能删
• 如果有多个奇环，所有奇环上的边都能删

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e4 + 5;

int n, m, tot, cut, col[MAXN], dep[MAXN], sum1[MAXN], sum2[MAXN], ind[MAXN];
vector<int> ans;

struct Edge {
	int v, id;
	Edge() {} Edge(int V, int Id) { v = V, id = Id; }
};
vector<Edge> G[MAXN];

void paint(int u, int c, int fa) {

	col[u] = c; dep[u] = dep[fa] + 1;

	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i].v;

		if (!col[v]) {
			paint(v, col[u] * -1, u);
			ind[v] = G[u][i].id;
			sum1[u] += sum1[v]; sum2[u] += sum2[v];
		} else if (dep[v] < dep[u] - 1) {
			if (col[v] == col[u]) cut = G[u][i].id, sum1[u]++, sum1[v]--, tot++;
			else sum2[u]++, sum2[v]--;
		}

	}
}

int main() {

	// freopen("CF19E.in", "r", stdin);
	// freopen("CF19E.out", "w", stdout);

	scanf("%d %d", &n, &m);
	for (int i = 1, u, v; i <= m; i++) {
		scanf("%d %d", &u, &v);
		G[u].push_back(Edge(v, i)); G[v].push_back(Edge(u, i));
	}

	for (int i = 1; i <= n; i++) if (!col[i]) paint(i, 1, 0);

	if (tot == 0) {
		printf("%d\n", m); for (int i = 1; i <= m; i++) printf("%d ", i);
		return 0;
	}

	if (tot == 1) {
		ans.push_back(cut);
	}

	for (int i = 1; i <= n; i++) if (sum1[i] == tot && !sum2[i]) {
		ans.push_back(ind[i]);
	}

	sort(ans.begin(), ans.end());
	ans.resize(unique(ans.begin(), ans.end()) - ans.begin());

	printf("%d\n", ans.size());
	for (int i = 0; i < ans.size(); i++) {
		printf("%d ", ans[i]);
	}

	return 0;
}