Here's the problem statement:
Problem statementYou are given a simple connected undirected graph with $$$N$$$ vertices numbered $$$1$$$ through $$$N$$$ and $$$M$$$ edges. The $$$i$$$-th edge connects vertices $$$a_i$$$ and $$$b_i$$$.
Determine whether there exists a cycle consisting of an odd number of vertices, and if one exists, find one such cycle.
Formally, determine whether there exists an integer sequence $$$(v_1,v_2,\ldots,v_K)$$$ satisfying all of the following conditions, and if one exists, find one such sequence.
- $$$K$$$ is an odd number at least $$$3$$$.
- $$$v_1,v_2,\ldots,v_K$$$ are all distinct.
- For every integer $$$i$$$ with $$$1\leq i\leq K$$$, there is an edge between vertices $$$v_i$$$ and $$$v_{i+1}$$$, where $$$v_{K+1}=v_1$$$.
Constraints
- $$$1\leq T\leq 2\cdot 10^5$$$
- $$$1\leq N,M\leq 2\cdot 10^5$$$
- The sum of $$$N$$$ over all test cases is at most $$$2\cdot 10^5$$$.
- The sum of $$$M$$$ over all test cases is at most $$$2\cdot 10^5$$$.
- $$$1\leq a_i,b_i\leq N$$$
- $$$a_i\neq b_i$$$
- The given graph is a simple connected undirected graph.
The author's solution proposes a method using a spanning tree, but I discovered a different approach (in contest) involving bipartite graphs, specifically revolving around this trivial observation:
ObservationIf a simple connected graph $$$G$$$ contains a cycle with odd length, then it will not be a bipartite graph. We can simply prove this by assuming the first vertex in the cycle with black then assign the other vertices colors in order before arriving a contradiction that the first vertex should be black and white.
We can also prove that if a simple connected graph $$$G$$$ doesn't contain a cycle with odd length then it must be bipartite by running a simple $$$BFS$$$ from $$$1$$$ and assign colors according to depth.
Therefore, we can solve the problem by first running a standard $$$BFS$$$ from $$$1,$$$ then checking if the graph is bipartite. This can be done by iterating through edges $$$(u, v)$$$ and check the parity of $$$d_u + d_v,$$$ with $$$d_i$$$ being the depth of the vertex $$$i$$$ after the $$$BFS$$$ from $$$1.$$$
If for all edges $$$(u, v),$$$ $$$d_u + d_v$$$ is odd then we can conclude that there are no odd cycles (and print $$$-1$$$).
If there exists an edge $$$(U, V)$$$ that $$$d_U + d_V$$$ is even then $$$(U, V)$$$ is an edge in a odd cycle.
This is where another array comes in, $$$from$$$. We define $$$from_i$$$ as the vertex that "adds" the node $$$i$$$ into the $$$BFS$$$ queue, and $$$from_1=-1$$$ (details are in the source code).
We can find the odd cycle like so: start with a deque with $$$U$$$ at the back and $$$V$$$ at the end and continuously assign $$$U := from_U$$$ and $$$V := from_V$$$ until $$$U=V,$$$ then we can push $$$U$$$ to the back and finish finding the odd cycle.
Source code (AC)//#pragma GCC optimize("O3", "Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m;
vector<int> g[N];
int from[N], d[N], dd[N];
void run(){
cin >> n >> m;
for (int i = 1; i <= m; i++){
int x, y; cin >> x >> y;
g[x].push_back(y); g[y].push_back(x);
}
if (m == n - 1){
cout << -1;
}
else {
queue<int> b;
d[1] = 0; b.push(1); from[1] = -1;
while (!b.empty()){
int u = b.front(); b.pop();
for (auto i : g[u]){
if (!dd[i]){
dd[i] = 1; from[i] = u; d[i] = d[u] + 1; b.push(i);
}
}
}
int u = -1, v = -1;
for (int i = 1; i <= n; i++){
for (auto j : g[i]){
if ((d[i] + d[j]) % 2 == 0){
u = i; v = j; break;
}
}
}
if (u == -1){
cout << -1;
}
else {
deque<int> x;
while (1){
if (u == v){
x.push_back(u); break; //final vertex of the odd cycle
}
x.push_back(u); x.push_front(v); //push from two ends
u = from[u]; v = from[v];
}
cout << x.size() << "\n";
for (auto i : x) cout << i << " ";
}
}
for (int i = 1; i <= n; i++){
g[i].clear(); dd[i] = 0; from[i] = 0; d[i] = 0; //resetting the array for future queries
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1; cin >> t;
while (t--){
run(); cout << "\n";
}
return 0;
}
