BZOJ 4424 -- Fairy

发表于 | 更新于 | 分类于 ， | 评论数：

摘要

给出一张无向图

删去一条边使之成为二分图

求那些边可行

题面

解

没有奇环，随意

否则必删奇环的交

而对于交中的树边，若它在某个偶环中，则不能删

若奇环只有一个，则它对应的非树边也可删（易知这条非树边必不在偶环中）

统计一条边所在奇环偶环数——打标记

Code

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
#include <cstdio>
#include <algorithm>

using std::sort;

const int MAXN=1000011, MAXM=1000011;

int N, M;

int Ans[MAXM], Ac;

int OddCnt, Odk;

struct Vert{
	int FE;
	int Dep;
	int C[2];
	bool Vis;
} V[MAXN];

struct Edge{
	int y, next, id;
} E[MAXM*2];

int Ecnt;

void addE(int a, int b, int c){
	++Ecnt;
	E[Ecnt].y=b;E[Ecnt].next=V[a].FE;V[a].FE=Ecnt;E[Ecnt].id=c;
}

bool Vis[MAXM];

void DFS(int at){
	for(int k=V[at].FE, to;k;k=E[k].next){
		if(Vis[E[k].id])	continue;
		Vis[E[k].id]=true;
		to=E[k].y;
		if(V[to].Dep){
			if((V[at].Dep-V[to].Dep)&1)
				{++V[at].C[0];--V[to].C[0];}
			else	{++OddCnt;Odk=k;++V[at].C[1];--V[to].C[1];}
		}
		else	{V[to].Dep=V[at].Dep+1;DFS(to);}
	}
}

void DFS_(int at){
	V[at].Vis=true;
	for(int k=V[at].FE, to;k;k=E[k].next){
		to=E[k].y;
		if(V[to].Vis)	continue;
		DFS_(to);
		V[at].C[0]+=V[to].C[0];
		V[at].C[1]+=V[to].C[1];
		if(V[to].C[1]==OddCnt && V[to].C[0]==0){
			Ans[++Ac]=E[k].id;
		}
	}
}

int main(){
	
	scanf("%d%d", &N, &M);
	
	for(int i=1, a, b;i<=M;++i){
		scanf("%d%d", &a, &b);
		addE(a, b, i);addE(b, a, i);
	}
	
	V[1].Dep=1;
	DFS(1);
	if(!OddCnt){
		printf("%d\n", M);
		for(int i=1;i<=M;++i)	printf("%d ", i);
		puts("");
		return 0;
	}
	DFS_(1);
	if(OddCnt==1)	Ans[++Ac]=E[Odk].id;
	
	sort(Ans+1, Ans+Ac+1);
	
	printf("%d\n", Ac);
	for(int i=1;i<=Ac;++i)	printf("%d ", Ans[i]);
	puts("");
	
	return 0;
}

/*
4 4
1 2
1 3
2 4
3 4

4
1 2 3 4

*/

/*
4 5
1 2
1 3
1 4
2 3
3 4

1
2

*/