【CF19E】【Bzoj4424】Fairy

来源和评测点

CF19E
Bzoj4424

题目

【题目大意】
给定n个点,m条边的无向图,可以从图中删除一条边,
问删除哪些边可以使图变成一个二分图。
(补充:只能是每次一条)
【输入格式】
第1行包含两个整数n,m。分别表示点数和边数。
第2到m+1行每行两个数x,y表示有一条(x,y)的边。
【输出格式】
输出第一行一个整数,表示能删除的边的个数。
接下来一行按照从小到大的顺序输出边的序号。
【输入样例】
4 4
1 2
1 3
2 4
3 4
【输出样例】
4
1 2 3 4

刷题记录

3h

分析

首先,确保理解题意无误后,各种画图探究二分图的性质
发现所谓二分图,就是不能有奇数环

长姿势:
对于一个图,可以考虑建立dfs序树,将边分为生成树边和返祖边(回边)
从而对于环或者之类的东西一目了然(因为树是没有环的)

然后在这里:DaD3zZ
它提到了单返祖边,但我并不觉得返祖边数量有任何影响
所以他的意思应该是,程序设计的时候,因为是建立dfs序树,所以只能处理单返祖边?

说说我的看法:
1.如果没有奇数环,那么输出所有边,因为这样都可以符合要求
2.1)必须删除的是奇数环的公共边,否则还会有奇数环剩余
2.2)不能是任何一个偶环的部分,否则会产生新的奇数环
引用几张图片,大家思考一下:


呃外站图片,懒得下载下来了,如果哪天csdn炸了(其实几率不大)或者文章删除了,评论即可。

打上标记输出即可
注意可能会有重边和负环,而且不一定联通。
负环:看作奇数环即可
重边:看作返祖边即可
联通:没进入过的进入即可
反正就是别太操心特殊情况,然后排除掉,要一视同仁~

写下来详细说说怎么dp吧(开始涉及细节了,想独立思考的请跳过)
先区分树边和返祖边,然后枚举返祖边判断环的奇偶性(有返祖边就有环)
如果奇数环个数=0,直接输出全部然后结束程序。
否则,如果是返祖边,如果奇数环=1,那么可以,否则显然就不是奇数环的公公共边了。
然后计算每条树边被多少个奇数环包含,从而判断是否是公共边
接下来用点来标记
网上好像没人说,但想半天后忽然发现,接下来这个其实类似于树上差分!
(解释一下,树上差分大概就是其他位置的树上前缀和不变)
每个点上面的odd、ever分别表示它的父亲树边在多少个偶数、奇数环中
回溯的时候再转移到边上,这样避免了处理双向边的繁琐,最后按顺序枚举输出。

最后的最后,补充一个降低代码复杂的方法,因为我们在建树的时候建立的是双向边,
令ln=1,然后这样建边的时候同一条边的编号一个是奇数一个是偶数,可以用异或处理了,而且除以2后就合并了。

真的是最后了,因为是双向建边,
可以向下的时候不能是(标记为不是返祖边),而是(标记为树边)
应该挺好理解的~

代码

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
111
112
113
114
//Zory-2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
//*******************全局常量*******************
const int MAXN=1000010;
//*******************全局定义*******************
struct road
{
int x,y;
int odd,even;//奇、偶
bool sb;//树边
}rd[MAXN];
struct nod
{
int hou;
int dep;
int odd,even;//奇、偶
}p[MAXN];
struct edge
{
int y,g;
}e[MAXN*2];
int ln=1;
void ins(int x,int y)
{
ln++;
e[ln].y=y;
e[ln].g=p[x].hou;
p[x].hou=ln;
}
//*******************实现*******************
bool v[MAXN];
void dfs1(int x,int dep)
{
p[x].dep=dep;v[x]=1;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(v[y]==0)
{
dfs1(y,dep+1);
rd[k/2].sb=1;
}
}
}
void dfs2(int x)
{
v[x]=1;//debug
for(int k=p[x].hou;k>0;k=e[k].g)
if(rd[k/2].sb=1)
{
int y=e[k].y;
if(v[y]==1) continue;//debug
dfs2(y);
p[x].odd+=p[y].odd;
p[x].even+=p[y].even;//树上前缀和
rd[k/2].odd=p[y].odd;
rd[k/2].even=p[y].even;
}
}
//*******************主函数*******************
int ans[MAXN];
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&rd[i].x,&rd[i].y);
rd[i].odd=rd[i].even=rd[i].sb=0;
ins(rd[i].x,rd[i].y);ins(rd[i].y,rd[i].x);
}
memset(v,0,sizeof(v));
for(int i=1;i<=n;i++) if(v[i]==0) dfs1(i,1);
int cnt=0;//奇数环个数
for(int i=1;i<=m;i++)
if(rd[i].sb==0)
{
int x=rd[i].x,y=rd[i].y;
if(p[x].dep>p[y].dep) swap(x,y);
if( (p[y].dep-p[x].dep)%2==1 ) p[x].even--,p[y].even++;//偶数环
else p[x].odd--,p[y].odd++,cnt++,rd[i].odd=1;//奇数环,特别处理一下返祖边
}
if(cnt==0)
{
printf("%d\n",m);
for(int i=1;i<=m;i++)
if(i<m) printf("%d ",i);
else printf("%d\n",i);
return 0;
}
memset(v,0,sizeof(v));
for(int i=1;i<=n;i++) if(v[i]==0) dfs2(i);
int ansn=0;
for(int i=1;i<=m;i++)
{
if(rd[i].sb)//树边
{
if(rd[i].even==0 and rd[i].odd==cnt) ans[++ansn]=i;
}
else//返祖边特判
{
if(rd[i].odd==cnt) ans[++ansn]=i;
}
}
printf("%d\n",ansn);
for(int i=1;i<=ansn;i++)
if(i<ansn) printf("%d ",ans[i]);
else printf("%d\n",ans[i]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/59cc.html
转载请注明出处,谢谢!