图是二分图的条件: 没有奇环
所以, 如果图不存在奇环, 删除任意一条边都可以
如果存在奇环,
对于树边来说:
那么可能可以删除的边一定在所有奇环的交集内
而且这条边不能在偶环内
因为如果一条边既是奇环上的一条边, 又是偶环上的一条边
删除这条边后, 这个奇环和偶环会合并成一个新的奇环
所以最终的答案 = 奇环的交集 - 偶环的并集
对于非树边来说:
如果只有一个奇环, 那么可以删除构成环的这条非树边
树边和非树边的判断: 并查集
奇环交与偶环并: 差分, 统计树上后缀和
- #include < cmath > #include < cstdio > #include < iostream > #include < algorithm > using namespace std;#define N 1000001 int e[N][2],
- ty[N];
- int tot = 1;
- int front[N],
- nxt[N << 1],
- to[N << 1],
- id[N << 1];
- int F[N];
- int maxd;
- int fa[N][21];
- int dep[N];
- int odd_cir,
- sum[N];
- int ans_tot,
- ans[N];
- void read(int & x) {
- x = 0;
- char c = getchar();
- while (!isdigit(c)) c = getchar();
- while (isdigit(c)) {
- x = x * 10 + c - 0;
- c = getchar();
- }
- }
- int find(int i) {
- return F[i] == i ? i: F[i] = find(F[i]);
- }
- void add(int u, int v, int num) {
- to[++tot] = v;
- nxt[tot] = front[u];
- front[u] = tot;
- id[tot] = num;
- to[++tot] = u;
- nxt[tot] = front[v];
- front[v] = tot;
- id[tot] = num;
- }
- void dfs(int u) {
- for (int i = 1; i <= maxd; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
- int t;
- for (int i = front[u]; i; i = nxt[i]) {
- t = to[i];
- if (t == fa[u][0]) continue;
- dep[t] = dep[u] + 1;
- fa[t][0] = u;
- dfs(t);
- }
- }
- int cal(int x) {
- for (int i = front[x]; i; i = nxt[i]) if (to[i] != fa[x][0]) {
- cal(to[i]);
- if (sum[to[i]] == odd_cir) ans[++ans_tot] = id[i];
- sum[x] += sum[to[i]];
- }
- }
- int get_lca(int u, int v) {
- if (dep[u] < dep[v]) swap(u, v);
- int cnt = dep[u] - dep[v];
- for (int i = maxd; i >= 0; --i) if (cnt & (1 << i)) u = fa[u][i];
- if (u == v) return u;
- for (int i = maxd; i >= 0; --i) if (fa[u][i] != fa[v][i]) u = fa[u][i],
- v = fa[v][i];
- return fa[u][0];
- }
- int main() {
- int n,
- m;
- int u,
- v,
- fu,
- fv;
- read(n);
- read(m);
- for (int i = 1; i <= n; ++i) F[i] = i;
- for (int i = 1; i <= m; ++i) {
- read(u);
- read(v);
- fu = find(u);
- fv = find(v);
- if (fu != fv) {
- ty[i] = 1;
- F[fu] = fv;
- add(u, v, i);
- }
- e[i][0] = u;
- e[i][1] = v;
- }
- maxd = log(n) / log(2);
- for (int i = 1; i <= n; ++i) if (find(i) == i) dep[i] = 1,
- dfs(i);
- int self = 0;
- int lca;
- for (int i = 1; i <= m; ++i) {
- u = e[i][0];
- v = e[i][1];
- if (u == v && self) {
- printf("0");
- return 0;
- }
- if (u == v) {
- self = i;
- continue;
- }
- if (!ty[i]) {
- lca = get_lca(u, v);
- if ((dep[u] - dep[lca] + dep[v] - dep[lca]) & 1) {
- sum[v]--;
- sum[u]--;
- sum[lca] += 2;
- } else {
- ty[i] = 2;
- odd_cir++;
- sum[v]++;
- sum[u]++;
- sum[lca] -= 2;
- }
- }
- }
- if (self) {
- if (!odd_cir) printf("1\n%d", self);
- else printf("0");
- return 0;
- }
- if (!odd_cir) {
- printf("%d\n", m);
- for (int i = 1; i < m; ++i) printf("%d", i);
- if (m) printf("%d", m);
- return 0;
- }
- for (int i = 1; i <= n; ++i) if (find(i) == i) cal(i);
- if (odd_cir == 1) for (int i = 1; i <= m; ++i) if (ty[i] == 2) {
- ans[++ans_tot] = i;
- break;
- }
- sort(ans + 1, ans + ans_tot + 1);
- printf("%d\n", ans_tot);
- for (int i = 1; i < ans_tot; ++i) printf("%d", ans[i]);
- if (ans_tot) printf("%d", ans[ans_tot]);
- }
- 4424 : Cf19E Fairy Time Limit: 10 Sec Memory Limit: 256 MB Submit: 740 Solved: 187[Submit][Status][Discuss] Description
给定 n 个点, m 条边的无向图, 可以从图中删除一条边, 问删除哪些边可以使图变成
一个二分图
Input
第 1 行包含两个整数 n,m 分别表示点数和边数
第 2 到 m+1 行每行两个数 x,y 表示有一条 (x,y) 的边
Output
输出第一行一个整数, 表示能删除的边的个数
接下来一行按照从小到大的顺序输出边的序号
- Sample Input
- 4 4
- 1 2
- 1 3
- 2 4
- 3 4
- Sample Output
- 4
- 1 2 3 4
- HINT
100% 的数据, n,m<=1000000
来源: http://www.bubuko.com/infodetail-2491536.html