题意
给定一个无向图，问删掉那条边使得给图可以变成一个二分图。
思路
回顾二分图的定义：不存在奇环的图。
由于不保证连通图，所以可以把整个图分成若干个连通块来考虑。
- 若所有连通块都是二分图：则此时删掉哪一条边剩下的都能形成二分图，答案是 \(m\).
- 若存在两个及以上的连通块是二分图：则此时不合法，删掉那一条边都一定会有二分图。
限制掉前两种后，接下来考虑只有一个连通块是二分图，于是可以转化为一个连通图的问题。
若删去一条边使得删完后不存在奇环，则删去的边一定满足以下条件：
- 在所有奇环中。
如果删去的边不在其中一个奇环里面，则连通图一定还存在一个奇环，此时不可能为二分图。 - 不在任意一个偶环中。
考虑要删的一条边，一定满足以下性质：
First.一定连通两个连通块。
Second.一定有一条另外的边联通两个连通块，形成一个奇环。
考虑到如果删去这条边的效果是可以给其中一个连通块的点都变色，才能使得染色不矛盾。
而此时若存在一个偶环，则变完色后偶环的点又会有矛盾了，即证。
![]()
然后接下来就是怎么来写了。
可以把连通图以 \(DFS\) 树的方式显现，则每一个环都存在一条返祖边，然后就可以用树上差分做了。
code
#include<bits/stdc++.h>
#define ll long longusing namespace std;const int N = 1e4+5;struct Edge{int to,nxt,id;
}e[N<<1];int tot=0,cnt=0,res=0;
int head[N],dep[N],s[N],fa[N],p;
bool flag=0;
bool vis[N];
vector<ll> vec;void add_Edge(int u,int v,int id){e[tot].to=v,e[tot].nxt=head[u],e[tot].id=id;head[u]=tot++;
}void dfs(int u,int f){dep[u]=dep[f]+1;fa[u]=f;vis[u]=1;for(int i=head[u];~i;i=e[i].nxt) {int v=e[i].to;if(v==f)continue;if(vis[v]){if(dep[v]<dep[u]){ll siz=dep[u]-dep[v]+1;if(siz&1)s[u]++,s[v]--,res++,flag=1,p=e[i].id;else s[u]--,s[v]++;}}else dfs(v,u);}
}void DFS(int u){vis[u]=1;for(int i=head[u];~i;i=e[i].nxt){int v=e[i].to,idx=e[i].id;if(vis[v])continue;DFS(v);s[u]+=s[v];if(s[v]==res)vec.push_back(idx);}
}
int n,m;
int main() {memset(head,-1,sizeof(head));cin>>n>>m;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;add_Edge(u,v,i);add_Edge(v,u,i);}for(int i=1;i<=n;i++){flag=0;if(!vis[i])dfs(i,0);if(flag){cnt++;if(cnt>1){cout<<-1;return 0;}memset(vis,0,sizeof(vis));DFS(i);}}if(cnt){if(res==1)vec.push_back(p);cout<<vec.size()<<"\n";sort(vec.begin(),vec.end());for(int i=0;i<vec.size();i++)cout<<vec[i]<<" ";}else {cout<<m<<"\n";for(int i=1;i<=m;i++)cout<<i<<" ";}return 0;
}