题解 CF19E 【Fairy】
hicc0305
2018-08-17 19:30:40
听说可以用LCT做。。。可是蒟蒻不会LCT。。。
首先,一个图一定是由一堆环和一堆链组成的。根据这道题,我们可以发现一个很好的性质,那就是,每一条链必然是一个二分图,每一个偶环,也必然是一个二分图,所以。。只剩下奇环。。不是二分图了。。
因此,我们要找的边是,被所有奇环覆盖的并且没有被偶环覆盖的边,因为,删掉这条边,原来的偶环变成了奇数条边,奇环变成了偶数条边,这两个环练了起来,又~~tm~~合成了一个奇环orz
也就是说我们要记录一条边被奇环和偶环覆盖的次数。覆盖的次数?怎么这么像运输计划。。因此我们想到了用树上差分来解决这个问题。
另外,这道题非常坑人,注意以下几点:
1.如果没有奇环,删那条边都可以,所以输出m条边
2.如果只有一个奇环,那么返祖边也要被算进答案。因为我们是用差分来求覆盖次数的,所以我们是从叶子节点往上,求子树和的,因此我们并不能遍历到返祖边,并没有把他算进答案。在有多个奇环的时候,返祖边是不可能能被算进答案的,因为返祖边只能覆盖自己的奇环(你可以在树上画画看),所以在有多个奇环的情况下,我们根本不用去管他。而在只有一个奇环的时候,他也要算进去了,做一个特判即可。当然,你把所有边领出来一起差分,把返祖边也差分到,是不用考虑这种情况的,这种情况只是针对在dfs的时候一起做差分的程序,这种程序是差分不到返祖边的(就像我)。
3.然后。。这道题其实还要考虑重边、自环。。。但是介于数据太水,你不去管也能过。。。
那么。。代码
```cpp
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int fa[2000010],tago[2000010],tage[2000010],dep[2000010];//tag是差分数组,dep记录深度,回到深度小的就是返祖边了
int fr[2000010],eve[2000010],odd[2000010],f[2000010],fz;//eve记录偶环差分和,odd记录奇环差分和,fz是对于只有一个奇环时,存返祖边的编号
int n,m,num;//num记录的是奇环个数
vector < pair<int,int> > to[2000010];
vector <int> ans;
void dfs(int u)
{
for(int i=0;i<to[u].size();i++)
{
int v=to[u][i].first;
if(v==fa[u]) continue;
if(!dep[v])
{
dep[v]=dep[u]+1;
fa[v]=u,fr[v]=to[u][i].second;
dfs(v);
eve[u]+=eve[v],odd[u]+=odd[v];
}
else if(dep[v]<=dep[u])//不要写成<,因为有自环情况要考虑(尽管这些数据是不会WA的)
{
if((dep[v]-dep[u])&1) tage[u]++,tage[v]--;//偶环情况
else num++,tago[u]++,tago[v]--,fz=to[u][i].second;//奇环情况
}
}
eve[u]+=tage[u];
odd[u]+=tago[u];
}
int solve()
{
int cnt=0;
if(!numoddn)//没有奇环
{
for(int i=1;i<=m;i++)
ans.push_back(i);
return m;
}
for(int i=1;i<=n;i++)
if(odd[i]==num && !eve[i])
{
cnt++;
ans.push_back(fr[i]);
}
if(num==1)//一个奇环
{
cnt++;
ans.push_back(fz);//加上返祖边
}
return cnt;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
int flag=1,it;
for(int j=0;j<to[x].size();j++)
if(to[x][j].first==y) flag=0,it=j;
if(flag)
{
if(x==y) to[x].push_back(make_pair(y,i));//处理自环
else to[x].push_back(make_pair(y,i)),to[y].push_back(make_pair(x,i));
}
else f[to[x][it].second]=1;//有重边就做标记
}
for(int i=1;i<=n;i++)
if(!dep[i])
{
dep[i]=1;
dfs(i);
}
int num=solve();
for(int i=0;i<ans.size();i++)
if(f[ans[i]]) ans.erase(ans.begin()+i),num--,i--;//如果选中的边中有重边,删掉
printf("%d\n",num);
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++)
printf("%d ",ans[i]);
return 0;
}
```