「bzoj4424」「Codeforces19E」Fairy - Dfs树+找环 | Bill Yang's Blog

「bzoj4424」「Codeforces19E」Fairy - Dfs树+找环

题目大意

给定$n$个点,$m$条边的无向图,可以从图中删除一条边,问删除哪些边可以使图变成一个二分图。


题目分析

二分图不能包含奇环,只能包含偶环,这是二分图的第二定义。
显然,我们要删除的边只能在奇环的交上
并不显然的还有:要删除的边不能在偶环上

为什么呢?如图:

删除红边后黑边会构成新的奇环,故删除的边不能在偶环上。

那么现在问题转化为了如何求出奇环的交。
利用以前在「APIO2010」巡逻 处遇到过求两个直径交的方法。
现在同样要用到这个技巧,我们对奇环每条边+1,对偶环每条边-1,最后权值为奇环个数的边即为交

我们可以在Dfs树上作差分操作来避免复杂的代码。(来自里阿奴摩西
注意Dfs树会少统计最后一条返祖边,这一条边我们标记下来,如果只有一个奇环就可以统计这条边。
为什么只用记录一条返祖边?
假设有一个奇环与奇环相邻,但是Dfs树统计的是一个小奇环和一个大偶环(奇环+奇环),故会无视掉第二个奇环输出返祖边。
假设有一个奇环与偶环相邻,Dfs树统计的是一个小奇环和一个大奇环(奇环+偶环),但是显然偶环上的边不能统计,故舍去。

此题还可以使用cdq左右逼近的方法做,明天来补坑。


代码

attention:本代码可以在cf通过,在bzoj提交会RE,因为bzoj会有一些毒瘤的重边和自环,当然这些重边自环已经处理,唯一没有处理的是手工栈,bzoj的数据中有一条一百万的单链,本人实在不想写手工栈了,请见谅。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=1000005*2;
int n,m,tmp,vst[maxn],Depth[maxn],sum[maxn],Ans[maxn],ans=0,cnt=0,Self_Circle,self=0;
struct Edge {
int from,to,id;
};
vector<Edge>edges;
vector<int>G[maxn];
void AddEdge(int x,int y,int id) {
edges.push_back((Edge) {
x,y,id
});
edges.push_back((Edge) {
y,x,id
});
int m=edges.size();
G[x].push_back(m-2);
G[y].push_back(m-1);
}
void Dfs(int Now,int father) {
vst[Now]=1;
for(int i=0; i<G[Now].size(); i++) {
Edge& e=edges[G[Now][i]];
int Next=e.to;
if(G[Now][i]==(father^1))continue;
if(!vst[Next]) {
Depth[Next]=Depth[Now]+1;
Dfs(Next,G[Now][i]);
sum[Now]+=sum[Next];
} else if(Depth[Next]<=Depth[Now]) {
if((Depth[Now]-Depth[Next]+1)&1) {
sum[Now]++;
sum[Next]--;
cnt++;
tmp=e.id;
} else {
sum[Now]--;
sum[Next]++;
}
}
}
}
void Find(int Now,int Up) {
vst[Now]=1;
if(sum[Now]==cnt)Ans[++ans]=Up;
for(int i=0; i<G[Now].size(); i++) {
Edge& e=edges[G[Now][i]];
int Next=e.to;
if(!vst[Next])Find(Next,e.id);
}
}
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
if(x==y) {
Self_Circle=i;
self++;
} else AddEdge(x,y,i);
}
for(int i=1; i<=n; i++)
if(!vst[i]) {
Depth[i]=1;
Dfs(i,-1);
}
if(cnt==0) { //没有奇环
if(self) { //子环
if(self==1)printf("1\n%d\n",Self_Circle);
else puts("0");
} else { //随便删边
printf("%d\n",m);
for(int i=1; i<=m; i++)printf("%d%c",i,i==m?'\n':' ');
}
} else { //有奇环
if(self)puts("0");
else {
memset(vst,0,sizeof(vst));
for(int i=1; i<=n; i++)
if(!vst[i])Find(i,0);
if(cnt==1)Ans[++ans]=tmp;
sort(Ans+1,Ans+ans+1);
printf("%d\n",ans);
for(int i=1; i<=ans; i++)printf("%d%c",Ans[i],i==ans?'\n':' ');
}
}
return 0;
}

姥爷们赏瓶冰阔落吧~
0%