CF19E Fairy

Posted on | Views:

树上差分.

二分图定义是能用黑白两种颜色给图染色,使得没有两个有边相连的节点颜色相同.其实也就是说图中不存在奇环.

那么一张二分图,删去任意一条边后一定仍是二分图.于是我们先做出原图的一棵生成树,再将剩下的边加入.

预处理 $LCA,dep$ ,然后加入非树边 $(u,v)$ .那么树上 $u\to v$ 路径上所有边都被这条非树边”覆盖”了.

若 $dis(u,v)$ 为奇,加入 $(u,v)$ 后会形成偶环,称这样的边为合法的边.

若 $dis(u,v)$ 为偶,则加入 $(u,v)$ 后会形成奇环,称这样的边为不合法的边.

记不合法的边总数为 $tot$ ,若 $tot=0$ ,可以删的边就是所有的边.

若 $tot=1$ ,可以删的边就是唯一的那条不合法边,以及树上被它覆盖,但未被合法边覆盖的边.

若 $tot>1$ ,可以删的边就是树上被所有不合法边覆盖,但未被任意一条合法边覆盖的边.

删去树边时要求未被合法边覆盖,是因为 $(u,v)$ 若被合法边覆盖,删去后 $u$ 可以走奇数步走到 $v$ ,图中仍存在奇环.

判断使用树上差分,被不合法边覆盖 $+1$ ,被合法边覆盖 $-1$ .

图可能有重边,自环,判起来比较麻烦.还可能不连通,需要每个联通块分别做上述步骤.

没有判重边/自环的代码

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e6+10;
int n,m,vis[MAXN];
vector<int> G[MAXN];
int color[MAXN];
struct Edge
{
	int u,v,id,tp;
	bool operator < (const Edge &rhs) const
	{
		return color[u]<color[rhs.u];
	}
}E[MAXN];
struct DSU
{
	int Fa[MAXN];
	void init()
	{
		for(int i=1;i<=n;++i)
			Fa[i]=i;
	}
	int Find(int x)
	{
		if(x==Fa[x])
			return x;
		return Fa[x]=Find(Fa[x]);
	}
	bool Union(int x,int y)
	{
		x=Find(x),y=Find(y);
		if(x==y)
			return false;
		Fa[x]=y;
		return true;
	}
}dsu;
void dfs_dye(int u,int col)
{
	color[u]=col;
	int t=G[u].size();
	for(int i=0;i<t;++i)
	{
		int v=G[u][i];
		if(color[v])
			continue;
		dfs_dye(v,col);
	}
}
typedef pair<int,int> pii;
map<pii,int> mp;
int fa[MAXN],dep[MAXN],siz[MAXN],mxson[MAXN],top[MAXN];
void dfs1(int u,int F)
{
	fa[u]=F;
	siz[u]=1;
	int t=G[u].size();
	for(int i=0;i<t;++i)
	{
		int v=G[u][i];
		if(v==F)
			continue;
		dep[v]=dep[u]+1;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[mxson[u]])
			mxson[u]=v;
	}
}
void dfs2(int u,int tp)
{
	top[u]=tp;
	if(mxson[u])
		dfs2(mxson[u],tp);
	int t=G[u].size();
	for(int i=0;i<t;++i)
	{
		int v=G[u][i];
		if(v==fa[u] || v==mxson[u])
			continue;
		dfs2(v,v);
	}
}
int LCA(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		x=fa[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
int rt[MAXN],L[MAXN],R[MAXN],delta[MAXN];
vector<int> ans;
void ins(int k)
{
	ans.push_back(E[k].id);
}
void dfs_sum(int u)
{
	int t=G[u].size();
	for(int i=0;i<t;++i)
	{
		int v=G[u][i];
		if(v==fa[u])
			continue;
		dfs_sum(v);
		delta[u]+=delta[v];
	}
}
int main()
{
	n=read(),m=read();
	dsu.init();
	int cnt=0;
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read();
		++cnt;
		E[cnt].u=u,E[cnt].v=v;
		E[cnt].id=i;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	m=cnt;
	int col=0;
	for(int i=1;i<=n;++i)
		if(!color[i])
		{
			rt[++col]=i;
			dfs_dye(i,col);
		}	
	sort(E+1,E+1+m);
	for(int i=1;i<=n;++i)
		G[i].clear();
	int curcol=1;
	L[1]=1;
	for(int i=1;i<=m;++i)
	{
		int u=E[i].u,v=E[i].v;
		if(color[u]!=curcol)	
		{
			R[curcol]=i-1;	
			++curcol;
			L[curcol]=i;
		}
		if(dsu.Union(u,v))//ontree
		{
			E[i].tp=1;
			G[u].push_back(v);
			G[v].push_back(u);
		}
		else
			E[i].tp=0;
	}
	R[curcol]=m;
	for(int i=1;i<=n;++i)
		if(!siz[i])
			dfs1(i,0);
	for(int i=1;i<=n;++i)
		if(!top[i])
			dfs2(i,i);
	for(int c=1;c<=curcol;++c)
	{
		int tot=0,tmp;
		for(int i=L[c];i<=R[c];++i)
		{
			if(E[i].tp)
				continue;
			int u=E[i].u,v=E[i].v,lca=LCA(u,v);
			int dis=dep[u]+dep[v]-2*dep[lca],val;
			if(dis&1)
				val=-1;
			else
			{
				++tot;
				val=1;
				tmp=i;
			}
			delta[u]+=val,delta[v]+=val;
			delta[lca]-=2*val;
		}
		if(!tot)
		{
			for(int i=L[c];i<=R[c];++i)
				ins(i);
		}
		else
		{
			dfs_sum(rt[c]);
			if(tot==1)
				ins(tmp);
			for(int i=L[c];i<=R[c];++i)
			{
				if(!E[i].tp)
					continue;
				int u=E[i].u,v=E[i].v;
				if(fa[u]==v)
					swap(u,v);
				if(delta[v]==tot)
					ins(i);
			}
		}
	}	
	sort(ans.begin(),ans.end());
	int t=ans.size();
	printf("%d\n",t);
	for(int i=0;i<t;++i)
		printf("%d ",ans[i]);
	return 0;
}