PROBLEM LINK:
Setter: Kasra Mazaheri
Tester: Arshia
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Observation, Finding Cycle in graph.
PROBLEM:
Given a graph with N junction and M one-way roads (u_i, v_i), Heinz chooses a start city and then performs the following alternatively.
- Walk his way from the current junction to another junction using any one-way road leading to that junction from current junction.
- Moonwalk his way out of his current junction to another junction by a one-way road leading from that junction to his current junction. When Heinz does this, he is actually breaking the law (since he is using the one-way road in the wrong direction), but since he is moonwalking, no one will notice.
Heinz plans to end up in the junction where he started after performing an even number of actions. However, he does not want to use any of the one-way roads more than once in any direction (using a road for both walking and moonwalking is not allowed either). It’s worth noting that Heinz must walk at least one one-way road. Can he achieve this goal? If he can, find a sequence of roads he should use.
QUICK EXPLANATION
- We can make a bipartite graph with 2*N vertices with undirected edges if for every one-way road (u, v) we add an undirected edge (u, N+v) in our bipartite graph.
- Solving the original problem is equivalent to finding a cycle in this new bipartite graph. Each cycle has even length in the bipartite graph.
- We can use BFS, DFS or any cycle finding algorithm to find any cycle in this graph, which starts from any node u such that 1 \leq u \leq N
EXPLANATION
From the statement, if Heinz has currently used x roads, he can use a road properly or moonwalk depending upon parity of x. If x is even, he uses the road normally, otherwise, he moonwalks.
Let us build a new graph with 2*N nodes. For a road (u, v) in original graph, lets add an undirected edge (u, v+N) in our new graph.
Lemma: The original problem is equivalent to finding a cycle in this new graph.
Proof:
- The resulting graph is bipartite with both partitions having size N, since for each edge (u, N+v) added in this graph, we had 1 \leq u \leq N and N+1 \leq N+v \leq 2*N.
- Moving from u to N+v in this graph correspond to moving from u to v using one way road (u, v).
- Moving from N+v to u in this graph correspond to moonwalking over edge (u, v), thus moving from v to u.
- Since this graph is bipartite, all cycles shall have even length, which follows by the definition of bipartite graphs.
- For nodes u such that 1 \leq u \leq N, all outgoing edges are to nodes N+v such that N+1 \leq N+v \leq 2*N which implies using one-way road. Now, from node N+v all outgoing edges are to nodes 1 \leq u \leq N which implies moonwalking. Hence, it is guaranteed that we use the road normally and moonwalk alternatively, which is required in the original problem.
Hence, the above claim reduces the problem of finding a cycle in this new bipartite graph.
We can use DFS, BFS to find a cycle in this graph, which may be referred here.
An important point to note here is that, if we find a cycle, the edges are to be printed so that the first edge is used as normal edge, the second edge is used for moonwalking, third edge is used as normal edge and so on. It is quite easy to get a WA missing this.
General idea for finding cycles
Start from an unvisited node and build a parent array, keeping track of ancestors. If a visited array is reached again, we can track the path till the first time the vertex was visited.
The same thing can be implemented by pushing vertices (or edge indices) into the stack and popping them out while printing answers.
TIME COMPLEXITY
Time complexity is O(N) per test case.
SOLUTIONS:
Setter's Solution
// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 400005;
int n, m, cv, cu, ce, M[N];
pair < int , int > P[N];
vector < pair < int , int > > Adj[N];
void DFS(int v)
{
M[v] = 1;
for (auto u : Adj[v])
if (u != P[v])
{
if (M[u.first] == 1)
cv = v, cu = u.first, ce = u.second;
else if (!M[u.first])
P[u.first] = {v, u.second}, DFS(u.first);
}
M[v] = 2;
}
inline void Solve()
{
cv = cu = ce = 0;
scanf("%d%d", &n, &m);
for (int i = 0; i <= n + n; i ++)
Adj[i].clear(), M[i] = 0, P[i] = {0, 0};
for (int i = 1; i <= m; i ++)
{
int v, u;
scanf("%d%d", &v, &u);
Adj[v].push_back({u + n, i});
Adj[u + n].push_back({v, i});
}
for (int i = 1; i <= n + n; i ++)
{
if (M[i])
continue;
DFS(i);
if (cv && cu)
{
vector < int > E = {ce};
while (cv != cu)
E.push_back(P[cv].second), cv = P[cv].first;
if (cu > n)
E.push_back(ce), E.erase(E.begin());
printf(":)\n%d\n", (int)E.size());
for (int id : E)
printf("%d ", id);
printf("\n");
return ;
}
}
printf(":(\n");
return ;
}
int main()
{
int q;
scanf("%d", &q);
for (; q; q --)
Solve();
return 0;
}
Tester's Solution
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
#define ll long long
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
//=======================================================================//
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
//=======================================================================//
const ll maxn=4e5+500;
bool vis[maxn];
ll s[maxn];
ll t[maxn];
vector<ll> ans;
vector<ll> ger[maxn];
ll b=-1;
bool dfs(ll a,ll p=-1){
vis[a]=1;
for(auto e:ger[a]){
ll tah=(s[e]^t[e]^a);
if(e!=p){
if(vis[tah]){
b=tah;
ans.pb(e);
return 1;
}else{
if(dfs(tah,e)){
if(b==-2){
return 1;
}
ans.pb(e);
if(a==b){
b=-2;
}
return 1;
}
}
}
}
return 0;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll q;
q=readIntLn(1,5);
while(q --){
ll n,m;
n=readIntSp(1,(ll)2e5);
m=readIntLn(1,(ll)2e5);
for(ll i=0;i<m;i++){
s[i]=readIntSp(1,n);
t[i]=readIntLn(1,n);
s[i]--;
t[i]--;
t[i]+=n;
ger[s[i]].pb(i);
ger[t[i]].pb(i);
}
ll ok=0;
for(ll i=0;i<2*n;i++){
if(!vis[i]){
if(dfs(i)){
cout<<":)\n"<<ans.size()<<endl;
if (t[ans[0]] != t[ans[1]])
ans.push_back(ans[0]), ans.erase(ans.begin());
for(auto v:ans){
cout<<v+1<<' ';
}
cout<<endl;
ok=1;
break;
}
}
}
if(ok==0){
cout<<":("<<endl;
}
for(ll i=0;i<2*n;i++){
ger[i].clear();
vis[i]=0;
ans.clear();
b=-1;
}
}
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class MNWLK{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni(), m = ni();
int[] from = new int[m], to = new int[m];
for(int i = 0; i< m; i++){
from[i] = ni()-1;
to[i] = ni()-1+n;
}
int[][] g = makeU(2*n, from, to);
boolean[] vis = new boolean[2*n];
for(int i = 0; i< n; i++){
if(vis[i])continue;
int end = dfs(g, from, to, vis, i, -1);
if(end != -1){
int[] ans = new int[m];
int c = 0;
int last = end;
do{
int ee = st.pop();
ans[c++] = ee;
end = from[ee]^to[ee]^end;
}while(end != last);
if(last > n){
int ee = ans[0];
for(int j = 0; j< c-1; j++)ans[j] = ans[j+1];
ans[c-1] = ee;
}
pn(":)");
pn(c);
for(int j = 0; j< c; j++)p(1+ans[j]+" ");pn("");
return;
}
}
pn(":(");
}
Stack<Integer> st = new Stack<>();
int dfs(int[][] g, int[] from, int[] to, boolean[] vis, int u, int p) throws Exception{
vis[u] = true;
for(int e:g[u]){
int v = from[e]^to[e]^u;
if(v == p)continue;
st.add(e);
if(vis[v])return v;
int nxt = dfs(g, from, to, vis, v, u);
if(nxt != -1)return nxt;
hold(e == st.pop());
}
return -1;
}
int[][] makeU(int n, int[]from, int[] to){
int[][] g = new int[n][];int[] cnt = new int[n];
for(int i:from)cnt[i]++;
for(int i:to)cnt[i]++;
for(int i = 0; i< n; i++)g[i] = new int[cnt[i]];
for(int i = 0; i< from.length; i++){
g[from[i]][--cnt[from[i]]] = i;
g[to[i]][--cnt[to[i]]] = i;
}
return g;
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new MNWLK().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 
