题解 CF19E 【Fairy】

一道妙题QAQ 首先我们知道判定是否为二分图的充要条件是有无奇环(很容易证的)，然后我们只要统计每个边在多少个奇环上就行了。 我们可以先按dfs序跑一棵树，因为dfs序跑的时候只可能会跑到返祖边(横叉边跑不到，可以反证)，于是我们就可以在树上跑来跑去，跑到返祖边的时候看一下当前环是奇还是偶，然后把环上的所有边的记录相应的环的种类都+1。 以上过程可以用差分做到$O(n)$ 判定的时候，如果是dfs树上的边，直接数经过它的奇环个数是否=奇环总个数，并且不能有偶环经过否则这条边就一定不能删。如果是dfs树上的返祖边，那它就至多有一个树上奇环经过它，判断一下它的奇环个数和总奇环个数是否都=1即可 ```cpp #include<bits/stdc++.h> #define fo(i, a, b) for (int i = (a); i <= (b); ++i) #define fd(i, a, b) for (int i = (a); i >= (b); --i) #define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v) #define N 10005 #define pb push_back #define F first #define S second #define ll long long #define inf 1000000007 #define mp std::make_pair #define lowbit(x) (x & -x) #define ls (k << 1) #define rs (k << 1 | 1) #define mod 100000007 #define eps 1e-4 #define itset std::set<node>::iterator #define lb lower_bound int head[N], u, v, n, m, ans[N], cans, p[N], fl[N]; struct edge{ int nxt, v, id; }e[N << 1]; int tot = 1, d[N]; int c1[N], c2[N], cnt; inline void addedge (int u, int v, int id) { e[++tot] = (edge) {head[u], v, id}; head[u] = tot; } inline void dfs (int u, int fa, int pre) { d[u] = d[fa] + 1; p[u] = e[pre].id; edge (i, u) { if ((i ^ pre) == 1) continue; if (!d[v]) { dfs(v, u, i); fl[e[i].id] = 1; c1[e[pre].id] += c1[e[i].id]; c2[e[pre].id] += c2[e[i].id]; } else { if (u == v && i & 1) { ++c1[e[i].id]; ++cnt; } else { if (d[u] > d[v]) if ((d[u] - d[v]) & 1) { ++c2[e[i].id]; ++c2[e[pre].id]; --c2[p[v]]; } else { ++c1[e[i].id]; ++c1[e[pre].id]; --c1[p[v]]; ++cnt; } } } } } int main () { scanf("%d %d", &n, &m); fo (i, 1, m) { scanf("%d %d", &u, &v); addedge(u, v, i); addedge(v, u, i); } fo (i, 1, n) if (!d[i]) dfs(i, 0, 0); if (!cnt) fo (i, 1, m) ans[++cans] = i; else fo (i, 1, m) if (fl[i]) { if (c1[i] == cnt && !c2[i]) { ans[++cans] = i; } } else { if (cnt == 1 && c1[i] == 1) ans[++cans] = i; } printf("%d\n", cans); fo (i, 1, cans) printf("%d ", ans[i]); return 0; } ```